Bissoy.com
Doctors Medicines MCQs Q&A

  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
4 views

1 Answers

Option 3 : 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.
4 views

Related Questions