The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged npda
0
votes
0
answers
1
Peter Linz Edition 4 Exercise 7.2 Question 18 (Page No. 196)
Give a construction by which an arbitrary contextfree grammar can be used in the proof of Theorem 7.1. Theorem 7.1: For any contextfree language L, there exists an npda M such that L = L (M).
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

12
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 7.2 Question 17 (Page No. 196)
Give full details of the proof of Theorem 7.2 . Theorem 7.2 : If L = L (M) for some npda M, then L is a contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

16
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
3
Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
Find a contextfree 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
by
Naveen Kumar 3
Boss
(
15.4k
points)

13
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

13
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
5
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. 191193) Example 7.8 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

13
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
1
answer
6
Peter Linz Edition 4 Exercise 7.2 Question 10 (Page No. 195)
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

28
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
1
answer
7
Peter Linz Edition 4 Exercise 7.2 Question 9 (Page No. 195)
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

43
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
8
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.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

12
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABBaAA,$ $A\rightarrow aBBa,$ $B\rightarrow bBBA.$
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

14
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 7.2 Question 4 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S → aSSSab$.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

6
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 7.2 Question 3 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbbaab$.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

13
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
12
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.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

12
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 7.1 Question 14 (Page No. 184)
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

5
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 7.1 Question 13 (Page No. 184)
What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

4
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
15
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)$} ?
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

10
views
theoryofcomputation
peterlinz
pushdownautomata
npda
0
votes
0
answers
16
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)$} ?
asked
Jun 22, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

7
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
17
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)$} ?
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

37
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 7.1 Question 8 (Page No. 183)
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

33
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 7.1 Question 7 (Page No. 183)
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

26
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 7.1 Question 6 (Page No. 183)
Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

29
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 7.1 Question 5 (Page No. 183)
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

16
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
22
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)$}.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

24
views
peterlinz
theoryofcomputation
pushdownautomata
npda
+1
vote
0
answers
23
Peter Linz Edition 4 Exercise 7.1 Question 3 (Page No. 183)
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

53
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 7.1 Question 2 (Page No. 183)
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.
asked
Apr 20, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

20
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
1
answer
25
TESTBOOK TEST SERIES
WHAT WILL BE THE ANS?
asked
Oct 3, 2018
in
Theory of Computation
by
Avik Chowdhury
Junior
(
639
points)

42
views
npda
0
votes
0
answers
26
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?
asked
Jul 15, 2018
in
Theory of Computation
by
Lakshay Kakkar
Active
(
2k
points)

43
views
peterlinz
theoryofcomputation
npda
+1
vote
2
answers
27
#Test series
Q. {al bm cn  l ≠ m or m ≠ n} construct a PDA for this language?
asked
Jul 10, 2018
in
Theory of Computation
by
himgta
Active
(
3.7k
points)

47
views
npda
0
votes
1
answer
28
Introduction to Computer Theory
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?
asked
Apr 13, 2018
in
Theory of Computation
by
The Capricorn
(
89
points)

86
views
theoryofcomputation
dpda
npda
+4
votes
0
answers
29
Introduction to Computer Theory
Construct a PDA for the language of all those strings in which the number of $b 's$ is double the number of $a 's$. $a$ and $b$ can occur in any order. For example: $L=\{\text{^}, abb, bab, bba, aabbbb, ababbb, abbbabb, abbbab, abbba, ...... \}$
asked
Mar 28, 2018
in
Theory of Computation
by
The Capricorn
(
89
points)

180
views
theoryofcomputation
npda
dpda
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 7.2 Question 6 (Page No. 195)
Construct a NPDA corresponding to the grammar. $S \rightarrow AAa$ $A\rightarrow SAb$ also convert the given grammar to GNF.
asked
Mar 25, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
36.5k
points)

244
views
theoryofcomputation
peterlinz
pushdownautomata
npda
Page:
1
2
next »
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
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged npda
Recent Blog Comments
In the question associated with the register of a...
@Dumbest Kid They call in 1:8 ratio, in 2018 212...
For how many questions I can raise an objection?
https://www.isro.gov.in/sites/default/files/comput...
Can someone please post official answer key link
50,737
questions
57,303
answers
198,306
comments
105,008
users