###### Question 9934 – Regular-Language

November 20, 2023###### Question 14201 – GATE 2021 CS-Set-1

November 20, 2023# Question 9342 – Regular-Language

If s is a string over (0 + 1)* then let n_{0}(s) denote the number of 0’s in s and n_{1}(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: n

State 2: n

State 3: n

State 4: n

State 5: n

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: n

Hence this is CFL.

Option B: The DFA contains 6 states

State 1: n

_{0}(s’) – n_{1}(s’) = 0State 2: n

_{0}(s’) – n_{1}(s’) = 1State 3: n

_{0}(s’) – n_{1}(s’) = 2State 4: n

_{0}(s’) – n_{1}(s’) = -1State 5: n

_{0}(s’) – n_{1}(s’) = -2State 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: n

_{0}(s) = 5 and n_{1}(s) = 1 then n_{0}(s) – n_{1}(s) = 4 and if n_{0}(s) = 15 and n_{1}(s) = 11 then n_{0}(s) – n_{1}(s) = 4.Hence this is CFL.

L = {s ∈ (0+1)* | n

_{0}(s) is a 3-digit prime}L = {s ∈ (0+1)* | for every prefix s’ of s,|n

_{0}(s’) – n_{1}(s’)| ≤ 2}L = {s ∈ (0+1)* |n

_{0}(s) – n_{1}(s)| ≤ 4}L = {s ∈ (0+1)* | n

_{0}(s) mod 7 = n_{1}(s) mod 5 = 0} Subscribe

Login

0 Comments