Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
What language is accepted by the pushdown automaton
$M=({q_0,q_1,q_2},\{a,b\},\{a,b,z\},\delta,q_0,z,\{q_2\})$
with
$\delta(q_0,a,a)=\{(q_0,aa)\}$
$\delta(q_0,b,a)=\{(q_0,ba)\}$
$\delta(q_0,a,b)=\{(q_0,ab)\}$
$\delta(q_0,b,b)=\{(q_0,bb)\}$
$\delta(q_0,a,z)=\{(q_0,az)\}$
$\delta(q_0,b,z)=\{(q_0,bz)\}$
$\delta(q_0,\lambda,b)=\{(q_1,b)\}$
$\delta(q_0,\lambda,a)=\{(q_1,a)\}$
$\delta(q_1,a,a)=\{(q_1,\lambda)\}$
$\delta(q_1,b,b)=\{(q_1,\lambda)\}$
$\delta(q_1,\lambda,z)=\{(q_2,z)\}$
$M=({q_0,q_1,q_2},\{a,b\},\{a,b,z\},\delta,q_0,z,\{q_2\})$
with
$\delta(q_0,a,a)=\{(q_0,aa)\}$
$\delta(q_0,b,a)=\{(q_0,ba)\}$
$\delta(q_0,a,b)=\{(q_0,ab)\}$
$\delta(q_0,b,b)=\{(q_0,bb)\}$
$\delta(q_0,a,z)=\{(q_0,az)\}$
$\delta(q_0,b,z)=\{(q_0,bz)\}$
$\delta(q_0,\lambda,b)=\{(q_1,b)\}$
$\delta(q_0,\lambda,a)=\{(q_1,a)\}$
$\delta(q_1,a,a)=\{(q_1,\lambda)\}$
$\delta(q_1,b,b)=\{(q_1,\lambda)\}$
$\delta(q_1,\lambda,z)=\{(q_2,z)\}$
Solution
In state $q_0$, the PDA reads input symbols and pushes them into the stack.So, first part of the string is stored in stack.
After that, using $\lambda$ move, PDA goes from $q_0$ to $q_1$.
In state $q_1$, the PDA reads input and matches it with the top of stack.
If input is $a$ and stack top is $a$, it pops $a$.
If input is $b$ and stack top is $b$, it pops $b$.
So, second part of the string must be reverse of the first part.
When stack reaches bottom symbol $z$, PDA goes to final state $q_2$.
Therefore, language accepted is even length palindrome over $\{a,b\}$.
So,
$L=\{ww^R\mid w\in\{a,b\}^+\}$
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
