The Gateway to Computer Science Excellence
0 votes


$\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \}$

$\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \} \cup \left \{ b^{n} | n\geq 0 \right \}$

$\left \{ \left ( b^{n}ab^{n}\right )^{m}a | n,m \geq 0 \right \}$



in Theory of Computation by Loyal (7.5k points)
edited by | 138 views
is it none?
Option C
I am getting none but answer given is A
Is it A?
The above PDA accepts by emptying the stack.So you push N b's onto the stack and then on seeing an a move to q1.In q1 pop each time for input b and if N b's are there then only z0 would be left on the stack.So on seeing an a move to z0.If the string is completely parsed then on seeing epsilon stack would be emptied and string would be accepted.Else the process could repeat again.So the language is of the form {(b^n a b^n a)^m|n,m>=0].
string 'aa' is generated by option it accepted by PDA ?
Correct answer is D, it will updated by them.
Yes it is accepted by the above PDA.On seeing a go to q1 and then on seeing a move to q0 and on seeing epsilon stack is emptied and hence it is accepted.
We cannot accept it, there is no transition with input A and top of stack as Zo
Oh yeah didn't notice that.In that case answer should be D.

@Hemanth_13 @Rutvik Reshamwala

cannot 'aa' accepted with these two transition

$\delta \left ( q_{0},a,X \right )=\left \{ q_{1},X \right \}$

$\delta \left ( q_{1},a,Z_{0} \right )=\left \{ q_{0},Z_{0} \right \}$

Why cannot it accepted?

But we need to X as top of the stack for this  @Srestha
I havenot got u

Plz tell more

X is pushing in stack

So, while popping with 'a' , why it is not on top on stack?
Ma'am for this transition δ(q0,a,X)={q1,X} we need X at top of stack but for string aa when we see first a we have z0 at top of stack and no move is defined for a when top of stack is z0 hence this transition is not possible.
oh yes

The string must start with b

a cannot starting of a string

Yes ma'am.If n>=1 was there then option A would be correct but in this case answer should be D.


this question ditto

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,352 answers
105,244 users