Language L1 is defined by the grammar: S1 → aS1 b |

Home » Theory of Computation » Theory of computation miscellaneous » Question

Language L₁ is defined by the grammar: S₁ → aS₁ b | ε
Language L₂ is defined by the grammar: S₂ → abS₂ | ε
Consider the following statements:
P : L₁ is regular
Q : L₂ is regular
Which one of the following is TRUE?

1. Both P and Q are true
2. P is true and Q is false
3. P is false and Q is true
4. Both P and Q are false

Correct Option: C

L1 has the property that no. of a’s should be equal to no. of b’s in a string, and all a’s should precede all b’s. Hence extra memory will be required to check this property of a string (Finite Automata can't be built for this type of language). Hence this is not regular language. Therefore P is False. L2 has the property that no. of a’s should be equal to no. of b’s, but order of a’s and b’s is different here, it is (ab)*, which will require no extra memory to be accepted. (Finite Automata can be built for this language). Hence L2 is regular language. Therefore Q is True.