search
Log In

Recent questions tagged pushdown-automata

2 votes
2 answers
1
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $(q,Y) \in \delta(p,a,X). $ Consider the ... $\Gamma = \{ \#, A\}$. The number of strings of length $100$ accepted by the above pushdown automaton is ___________
asked Feb 18 in Theory of Computation Arjun 538 views
1 vote
3 answers
2
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 584 views
1 vote
2 answers
3
0 votes
0 answers
4
A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 116 views
0 votes
0 answers
5
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more powerful (recognize a larger class of languages) than $0-PDAs$. Show that $2-PDAs$ are more powerful than $1-PDAs$. Show that $3-PDAs$ are not more powerful than $2-PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 57 views
0 votes
0 answers
6
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 329 views
0 votes
0 answers
7
0 votes
0 answers
9
Find a context-free grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions $δ(q_0, a,z) =$ {$(q_0, Az)$}, $δ (q_0,b, A) =$ {$(q_0, AA)$}, $δ(q_0, a, A) =$ {$(q_1,λ)$}.
asked Jun 23, 2019 in Theory of Computation Naveen Kumar 3 73 views
0 votes
0 answers
11
Show that the npda in Example 7.8 accepts L (aa*b). Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b). show that the variable ($q_0zq_1$) is useless. (see page no. 191-193) Example 7.8 : Consider the npda with transitions $\delta(q_0,a,z)=$ ... $(q_0,A)$}, $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
asked Jun 23, 2019 in Theory of Computation Naveen Kumar 3 82 views
0 votes
0 answers
14
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$. Show how the number of states of $\widehat M $ in the above exercise can be reduced to two.
asked Jun 22, 2019 in Theory of Computation Naveen Kumar 3 76 views
0 votes
0 answers
19
Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the language generated by the given grammar. Example 7.6: Construct a pda that accepts the language generated by a grammar with productions $S\rightarrow aSbb|a.$
asked Jun 22, 2019 in Theory of Computation Naveen Kumar 3 65 views
0 votes
0 answers
20
We can define a restricted npda as one that can increase the length of the stack by at most one symbol in each move, changing Definition 7.1 so that $\delta :$Q x $(\sum \cup$ {$\lambda$}$) $ $ \Gamma \rightarrow 2^{Q (\Gamma \Gamma \cup \Gamma \cup {\lambda})}$ The ... , $q_0 ∈ Q$ is the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.
asked Jun 22, 2019 in Theory of Computation Naveen Kumar 3 250 views
0 votes
0 answers
23
What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) with transitions $\delta(q_0,a,z)=${$(q_1,a),(q_2,\lambda)$}, $\delta(q_1,b,a)=${$(q_1,b)$}, $\delta(q_1,b,b)=${$(q_1,b)$}, $\delta(q_1,a,b)=${$(q_2,\lambda)$} ?
asked Jun 22, 2019 in Theory of Computation Naveen Kumar 3 55 views
0 votes
0 answers
24
What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}), with $\delta(q_0,b,z)=${$(q_1,1z)$}, $\delta(q_0,b,1)=${$(q_1,11)$}, $\delta(q_2,a,1)=${$(q_3,\lambda)$}, $\delta(q_3,a,1)=${$(q_4,\lambda)$} $\delta(q_4,a,z)=${$(q_4,z),(q_5,z)$} ?
asked Jun 22, 2019 in Theory of Computation Naveen Kumar 3 51 views
1 vote
1 answer
25
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack. DPDA with empty stack accepts LR(0) grammar. Can someone explain in depth/or give good reference links?
asked May 13, 2019 in Theory of Computation manisha11 231 views
0 votes
0 answers
26
0 votes
0 answers
27
0 votes
0 answers
29
Give informal English descriptions of PDAs for the following languages. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$ The complement of the language $\{a^{n}b^{n}|n\geq 0\}$ $\{w\#x|w^{R}$ $\text{is a substring of $x$ for }$ $w,x \in\{0,1\}^{*}\}$ ... $\text{each}$ $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
asked May 1, 2019 in Theory of Computation Lakshman Patel RJIT 70 views
...