Bissoy.com
Doctors Medicines MCQs Q&A

  1. L = { an bn |n ≥ 0} and is not accepted by any finite automata
  2. L = { an | n ≥ 0} ∪ { anbn | n ≥ 0} and is not accepted by any deterministic PDA
  3. L is not accepted by any Turing machine that halts on every input
  4. L = { an|n ≥ 0} ∪ {anbn|n ≥ 0} and is deterministic context-free
4 views

1 Answers

Option 4 : L = { an|n ≥ 0} ∪ {anbn|n ≥ 0} and is deterministic context-free

Concept:

Acceptance of given string by a push down automata in two ways either by

  • Acceptance by final state: if machine at the end of the string enters to one of the final states then string is accepted.

  • Acceptance by Empty state: if at the end of the string, stack is empty then string is accepted.

Explanation:

In this PDA, initial state is also the final state it means null string is accepted by the given push down automata (PDA). Consider the states as q1, q2 and q3 where q1 is the final state.

Transition of given PDA are:

1) (q1, a, Z) => (q1, XZ)

2) (q1, a, X) => (q1, XX)

3) (q1, b, X) => (q2, ϵ)

4) (q2, b, X) => (q2, ϵ)

5) (q2, ϵ, Z) => (q3, Z)

First two transition show that after giving input a at transition state remains same. With every input ‘a’ we push X into stack. It means an is always accepted for n>= 0. Transition 3 and 4 shows that for every b input a X is popped out of the stack until stack symbol is Z and string becomes empty. It means ‘b’ occurred same number of times as ‘a’. It represents language of the form {anbn for n>=0 }. It is a DCFL.
4 views

Related Questions