menu
search
Log In
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

Subjects

Recent questions tagged npda

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged npda

0 votes
2 answers
1
NIELIT 2017 DEC Scientific Assistant A - Section B: 6
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 275 views
0 votes
6 answers
2
NIELIT 2017 DEC Scientist B - Section B: 39
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 1.9k views
0 votes
0 answers
3
Peter Linz Edition 4 Exercise 7.2 Question 18 (Page No. 196)
Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1. Theorem 7.1: For any context-free language L, there exists an npda M such that L = L (M).
Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1. Theorem 7.1: For any context-free language L, there exists an npda M such that L = L (M).
asked Jun 23, 2019 in Theory of Computation Naveen Kumar 3 47 views
0 votes
0 answers
5
Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
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,λ)$}.
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 70 views
0 votes
0 answers
7
Peter Linz Edition 4 Exercise 7.2 Question 11,12,13 (Page No. 195)
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 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
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 69 views
0 votes
0 answers
10
Peter Linz Edition 4 Exercise 7.2 Question 7,8 (Page No. 195)
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.
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 63 views
0 votes
0 answers
14
Peter Linz Edition 4 Exercise 7.1 Question 16 (Page No. 184)
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$}$) $ ... the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.
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 212 views
0 votes
0 answers
17
Peter Linz Edition 4 Exercise 7.1 Question 11 (Page No. 184)
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)$} ?
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 50 views
0 votes
0 answers
18
Peter Linz Edition 4 Exercise 7.1 Question 10 (Page No. 184)
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)$} ?
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 45 views
0 votes
0 answers
19
Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?
asked Apr 20, 2019 in Theory of Computation Naveen Kumar 3 95 views
0 votes
0 answers
24
Peter Linz Edition 4 Exercise 7.1 Question 4 (Page No. 183)
Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}. (a) $L =$ {$a^nb^{2n} : n ≥ 0$}. (b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}. (c) $L =$ {$a^nb^mc^{n+m} : n ≥ 0, m ≥ 0$}. (d) $L =$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.
Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}. (a) $L =$ {$a^nb^{2n} : n ≥ 0$}. (b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}. (c) $L =$ {$a^nb^mc^{n+m} : n ≥ 0, m ≥ 0$}. (d) $L =$ {$a^nb^{n+m}c^m : n ≥ 0, m ≥ 1$}. (e) $L =$ {$a^3b^nc^n : n ≥ 0$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.
asked Apr 20, 2019 in Theory of Computation Naveen Kumar 3 52 views
0 votes
1 answer
27
TESTBOOK TEST SERIES
WHAT WILL BE THE ANS?
WHAT WILL BE THE ANS?
asked Oct 3, 2018 in Theory of Computation Avik Chowdhury 74 views
0 votes
0 answers
28
Existence of a 2 state NPDA
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
asked Jul 15, 2018 in Theory of Computation Lakshay Kakkar 96 views
1 vote
2 answers
29
#Test series
Q. {al bm cn | l ≠ m or m ≠ n} construct a PDA for this language?
Q. {al bm cn | l ≠ m or m ≠ n} construct a PDA for this language?
asked Jul 10, 2018 in Theory of Computation himgta 93 views
0 votes
1 answer
30
Introduction to Computer Theory
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?
asked Apr 13, 2018 in Theory of Computation The Capricorn 147 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...