Register

Push down automata - Theory of computation. Gate CSE

349 views
1 votes
1 votes

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

User Avatar

2 Answers

Best answer
1 votes
1 votes
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
User Avatar
2 votes
2 votes
You can't.This isn't context free.Intutively you require two comparisons but rigorous proof can be given by pumping lemma.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
2
Alakhator asked Nov 11, 2018
894 views
Push Down Automata
Construct a PDA for set of strings over {a,b,c,d} such that L={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}
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}
User Avatar
0 votes
0 votes
1 answer
3
Abhisek Tiwari 4 asked Nov 6, 2018
716 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 Then A)Ldf proper subset of Lef. B)Ldf = Lef. C)Lef proper subset of Ldf. D)None .
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 ...
User Avatar
Link Copied!