Register

Push down automata - Theory of computation. Gate CSE

598 views
1 1 vote

How to draw the diagram for language = {am bxcmdx} accepted by non deterministic PDA?

2 Answers

Best answer
1 1 vote
Language given by you is not CFL, therefore, you cannot draw PDA and NPDA for this language but yes you can construct a Turing machine for this language. Above Language is CSL.
• selected by
2 2 votes
You can't.This isn't context free.Intutively you require two comparisons but rigorous proof can be given by pumping lemma.
Voting & Accepting an answer helps improve the community
← Previous · solve seriesNext → · Static variable doub...
← Previous in category · Test seriesNext in category → · Undecidability Confu...
Position:
Show:

Related questions

0 0 votes
1 1 answer
876
876 views
Na462 asked Jan 19, 2019
876 views
Ace Test Series 2019: Theory Of Computation - Push Down Automata
0 0 votes
1 1 answer
254
254 views
manjeet singh asked Dec 15, 2024
254 views
My question about push down automata is when FA With stack read the input from the input tape then why it is moving left to right only . simply i reapeat my doubt is when PDA read input then after reading the input why is move in right direction only ???
0 0 votes
2 2 answers
1.3k
1.3k views
Alakhator asked Nov 11, 2018
1,258 views
Push Down Automata
Construct a PDA for set of strings over {a,b,c,d} such thatL={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}
0 0 votes
1 1 answer
1.2k
1.2k views
Abhisek Tiwari 4 asked Nov 6, 2018
1,170 views
Push Down Automata
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack ThenA)Ldf proper subset of Lef.B)Ldf = Lef.C)Lef ...