Register

Recent questions tagged pushdown-automata

0 votes
2 answers
181
dpda }} Linz7.3-4
DPDA for $L = \left \{ a^nb^n:n\geq 1 \right \} \cup\left \{ a \right \}$
DPDA for $L = \left \{ a^nb^n:n\geq 1 \right \} \cup\left \{ a \right \}$
User Avatar
0 votes
2 answers
182
dpda || Linz 7.3-2
DPDA for $L = \left \{ a^nb^m|m\geq n+2 \right \}$
DPDA for $L = \left \{ a^nb^m|m\geq n+2 \right \}$
User Avatar
0 votes
0 answers
184
Construction of PDA
Can someone construct a PDA for ai bj where i not equal to 3j+1 ? Is it NPDA or DPDA?
Can someone construct a PDA for ai bj where i not equal to 3j+1 ? Is it NPDA or DPDA?
User Avatar
2 votes
1 answer
185
Language Accepted By PDA
Please Explain why the following is accpeted/rejected by PDA . ( Need detail explanation ) S1 = { 0n 0m 1n 0m | n,m>0 } S2 = { 0n 0m 1n 1m 0m | n,m>0 } S3 = { am 0m 1n 1n | n,m>0} S4 = { am 0n 1n 1m | n,m>0}
Please Explain why the following is accpeted/rejected by PDA . ( Need detail explanation )S1 = { 0n 0m 1n 0m | n,m>0 }S2 = { 0n 0m 1n 1m 0m | n,m>0 }S3 = { am 0m 1n...
User Avatar
1 votes
2 answers
186
PDA construction
Is the following language context free L = {$0^{i}1^{j}, i=2j+1$} How can PDA be designed for this language?
Is the following language context freeL = {$0^{i}1^{j}, i=2j+1$}How can PDA be designed for this language?
User Avatar
0 votes
1 answer
187
Equivalency of diffetent automata
Write about the equivalency of different automata such as DFA, NFA, DPDA, NPDA, DTM, NTM. Which automata or machine can be converted to other machines and why? For example NFA can be converted to DFA, DPDA, NPDA, DTM, NTM.
Write about the equivalency of different automata such as DFA, NFA, DPDA, NPDA, DTM, NTM. Which automata or machine can be converted to other machines and why? For exampl...
User Avatar
4 votes
2 answers
188
Doubts
$a^{2n}b^n$ $a^nb^m, m\leq n\leq 3m$ $a^nb^m , n=4m$ Which of the following is CFL ?
$a^{2n}b^n$$a^nb^m, m\leq n\leq 3m$$a^nb^m , n=4m$Which of the following is CFL ?
User Avatar
1 votes
1 answer
189
TOC-PDA
IS one state sufficient for an empty stack PDA? Needs explanation !
IS one state sufficient for an empty stack PDA?Needs explanation !
User Avatar
1 votes
0 answers
191
UGC NET CSE | September 2013 | Part 3 | Question: 22
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ ...
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ is$\delta (q_0, \lambda , z)= \{ (q_1, z) \}; \delta...
User Avatar
2 votes
1 answer
192
NPDA
How much memory does npda takes or has? As when we are taking npda for let's say ww^r.. Then we will be considering two pda at the same time.. Is it practical or theoretical.. Whts the case?
How much memory does npda takes or has? As when we are taking npda for let's say ww^r.. Then we will be considering two pda at the same time.. Is it practical or theoret...
User Avatar
1 votes
1 answer
194
Pushdown automata
For every pushdown automata,there exists an equivalent A)Regular Language B)Context sensitive language C)Context free language D)Recursively Enumerable language.
For every pushdown automata,there exists an equivalentA)Regular LanguageB)Context sensitive languageC)Context free languageD)Recursively Enumerable language.
User Avatar
0 votes
1 answer
196
Pushdown automation
A language L is accepted by a pushdown automation if and only if it is A) Context Sensitive B)Recursive C)Context Free D)Right Linear
A language L is accepted by a pushdown automation if and only if it isA) Context SensitiveB)RecursiveC)Context FreeD)Right Linear
User Avatar
0 votes
1 answer
198
DESIGN PDA
THE SET OF ALL STRINGS OF a's and b's THAT ARE NOT OF THE FORM ww, i.e., NOT EQUAL TO ANY STRING REPEATED
THE SET OF ALL STRINGS OF a's and b's THAT ARE NOT OF THE FORM ww, i.e., NOT EQUAL TO ANY STRING REPEATED
User Avatar
0 votes
1 answer
199
TOC , Language ,PDA
What does this Language Represents ? And what is the machine which is able to represent this Language. L = { a^i b^j c^k d^l } where i = k or j = l How it is different from L = {a^m b^n c^m d^n}
What does this Language Represents ? And what is the machine which is able to represent this Language.L = { a^i b^j c^k d^l } where i = k or j = lHow it is different fro...
User Avatar
1 votes
2 answers
200
Automata Language PDA
If a given CFL Language is L= {a^n b^n ;n>=0} then how can we determine the value of L^2 .Explain with an example .
If a given CFL Language is L= {a^n b^n ;n>=0} then how can we determine the value of L^2 .Explain with an example .
User Avatar
1 votes
2 answers
206
Push down automata
Which solution is correct one? I wish I solved it correctly (sol1)
Which solution is correct one?I wish I solved it correctly (sol1)
User Avatar
1 votes
0 answers
207
Output Of PDA.
User Avatar
5 votes
4 answers
208
PDA
Consider the following push down automata. The language accepted by above PDA is_______. Regular but infinite. DCFL but not regular. CFL but not DCFL Finite language.
Consider the following push down automata.The language accepted by above PDA is_______.Regular but infinite.DCFL but not regular.CFL but not DCFLFinite language.
User Avatar
1 votes
1 answer
209
Theory of computation question
http://geeksquiz.com/gate-gate-cs-2015-set-1-question-60/ please give explanation to this question.
http://geeksquiz.com/gate-gate-cs-2015-set-1-question-60/please give explanation to this question.
User Avatar
0 votes
2 answers
210
how to construct pda for a^i b^j where j!=2i+1, i>=0
how to construct pda for a^i b^j where j!=2i+1, i>=0 ? i have constructed for j=2i+1 but by complementing the states do we get actual n pda of our requirement? whether it is decidable?
how to construct pda for a^i b^j where j!=2i+1, i>=0 ?i have constructed for j=2i+1 but by complementing the states do we get actual n pda of our requirement?whether it i...
User Avatar
Page: