Question 9934 – Regular-Language
November 20, 2023Question 14201 – GATE 2021 CS-Set-1
November 20, 2023Question 9342 – Regular-Language
If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular?
Correct Answer: C
Question 5 Explanation:
Since 3-digit prime numbers are finite so language in option A is finite, hence it is regular.
Option B: The DFA contains 6 states
State 1: n0(s’) – n1(s’) = 0
State 2: n0(s’) – n1(s’) = 1
State 3: n0(s’) – n1(s’) = 2
State 4: n0(s’) – n1(s’) = -1
State 5: n0(s’) – n1(s’) = -2
State 6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n0(s) = 5 and n1(s) = 1 then n0(s) – n1(s) = 4 and if n0(s) = 15 and n1(s) = 11 then n0(s) – n1(s) = 4.
Hence this is CFL.
Option B: The DFA contains 6 states
State 1: n0(s’) – n1(s’) = 0
State 2: n0(s’) – n1(s’) = 1
State 3: n0(s’) – n1(s’) = 2
State 4: n0(s’) – n1(s’) = -1
State 5: n0(s’) – n1(s’) = -2
State 6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n0(s) = 5 and n1(s) = 1 then n0(s) – n1(s) = 4 and if n0(s) = 15 and n1(s) = 11 then n0(s) – n1(s) = 4.
Hence this is CFL.
L = {s ∈ (0+1)* | n0(s) is a 3-digit prime}
L = {s ∈ (0+1)* | for every prefix s’ of s,|n0(s’) – n1(s’)| ≤ 2}
L = {s ∈ (0+1)* |n0(s) – n1(s)| ≤ 4}
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod 5 = 0}
Subscribe
Login
0 Comments