Language L1 is defined by the grammar: S1 → aS1b|ϵ Language L2 is defined by the grammar: S2 → abS2|ϵ Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?
Language L1 is defined by the grammar: S1 → aS1b|ϵ Language L2 is defined by the grammar: S2 → abS2|ϵ Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE? Correct Answer P is false and Q is true
Suppose grammar G1:
S1 → aS1b|ϵ
It generates language in which number of a’s are equal to number of b’s and all a’s are followed by b’s
L1 = { an bn | n ≥ 0}.
It is deterministic context free language. Extra memory is required for this. So, it can’t be accepted by finite state automata. L1 is not a regular language.
Now, another grammar let G2: S2 → abS2|ϵ
This grammar also generates language in which number of a’s are equal to number of b’s. But it generates language L2 = { (ab)n | n ≥ 0 }
Regular expression for this = (ab)*
It doesn’t require any extra memory to remember the last string. It can be accepted by finite state automata. So, L2 is regular.