Gate Bits 2 CFL and PDA
In this class, We discuss Gate Bits 2 CFL and PDA.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of the concepts CFL and PDA. Click Here.
Gate 2017:
Identify the language generated by the following grammar, where S is the start variable.
S→XY
X→aX∣a
Y→aYb∣ϵ
1) {a^mb^n ∣m≥n,n>0}
2) {a^mb^n ∣m≥n,n≥0}
3) {a^mb^n ∣m>n,n≥0}
4) {a^mb^n ∣m>n,n>0}
Answer: 3
Gate 97:
Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?
a. {wcwR ∣ w∈ {a,b}* }
b. {wwR ∣ w∈ {a,b,c}* }
c. {anbncn ∣ n ≥ 0 }
d. {w ∣ w is a palindrome over {a,b,c} }
Note: wR is the string obtained by reversing ‘w‘
1) a
2) b
3) c
4) d
Answer: 1
Explanation Provided in the video.