Push-Down-Automata

Question 1

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

A
L = {an bn│n ≥ 0} and is not accepted by any finite automata
B
L = {an |n≥0} ∪ {anbn|n ≥ 0} and is not accepted by any deterministic PDA
C
L is not accepted by any Turing machine that halts on every input
D
L = {an |n ≥ 0} ∪ {an bn |n ≥ 0} and is deterministic context-free
Question 1 Explanation: 
In this PDA, we can give labels to state as q0, q1, q2
where q0 and q2 are final states.
This PDA accepts the string by both ways i.e. by using q0 accepts as final state and by using q2 it accepts as empty stack.
Since q0 is initial as well as final state, so it can accept any number of a’s (including zero a’s) and by using q2 as empty stack it accept strings which has equal number of a’s and b’s (b’s comes after a’s).
Hence, L = {an | n≥0} ∪ { an bn | n≥0}.
Question 2

Consider the following languages over the alphabet Σ = {0,1,c}:

    L1 = {0n1n | n≥0}
    L2 = {wcwr | w∈{0,1}*}
    L3 = {wwr | w∈{0,1}*}

Here, wr is the reverse of the string . Which of these languages are deterministic Context-free languages?

A
None of the languages
B
Only L1
C
Only L1 and L2
D
All the three languages
Question 2 Explanation: 
L1 and L2 are DCFL, as we can design DPDA for them. For L1, DPDA will first push all zero’s in stack and when one appears in string, it will pop zero for every one and at the end if input string as well as stack is empty then accept the string else reject the string. Similarly for L2, DPDA will push all the string till it encounter the terminal “c” and once “c” appears in string, DPDA will ignore this “c” and then for every terminal in string (after “c”) it will pop one symbol from stack and match, if matched then pop next and continue. If didn’t match at any stage then reject the string. Since push and pop is clearly defined (i.e., every transition is deterministic), so both L1 and L2 is DCFL.
But in L3, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L3 is not possible. It can be accepted by NPDA only, so L3 is CFL but not DCFL.
Question 3

Give a deterministic PDA for the language L = {ancb2n|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.

A
Theory Explanation is given below.
There are 3 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access