Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged peter-linz
0
votes
0
answers
31
Peter Linz Edition 4 Exercise 7.3 Question 1 (Page No. 200)
Show that $L =$ {$a^nb^{2n} : n ≥ 0$} is a deterministic context-free language.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
150
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
0
votes
0
answers
32
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).
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
222
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
33
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 context-free language.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
219
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
34
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,λ)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
234
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
35
Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
220
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
36
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)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 23, 2019
by
Naveen Kumar 3
271
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
1
answer
37
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
313
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
2
answers
38
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
971
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
39
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
177
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
40
Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
182
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
1
answer
41
Peter Linz Edition 4 Exercise 7.2 Question 4 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
234
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
42
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 aSbb|aab$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
150
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
43
Peter Linz Edition 4 Exercise 7.2 Question 2 (Page No. 195)
Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
134
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
0
votes
0
answers
44
Peter Linz Edition 4 Exercise 7.2 Question 1 (Page No. 195)
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.$
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
157
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
0
votes
0
answers
45
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.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
554
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
46
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^*)$.
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
202
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
47
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$}?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
136
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
48
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
169
views
theory-of-computation
peter-linz
peter-linz-edition4
pushdown-automata
npda
0
votes
0
answers
49
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Jun 22, 2019
by
Naveen Kumar 3
160
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
2
votes
1
answer
50
Peter LInz Edition 6 Exercise 1.3
Q)Let x and y be two positive binary numbers.Design a transducer whose output is max(x,y).
suraj prasad shaw
asked
in
Theory of Computation
May 26, 2019
by
suraj prasad shaw
335
views
peter-linz
theory-of-computation
0
votes
1
answer
51
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)$} ?
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
362
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
52
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
272
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
53
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.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
178
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
54
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
223
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
55
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
155
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
56
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)$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
252
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
0
answers
57
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)
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
395
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
0
votes
0
answers
58
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
123
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
npda
1
vote
0
answers
59
Peter Linz Edition 4 Exercise 7.1 Question 1 (Page No. 183)
Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 20, 2019
by
Naveen Kumar 3
265
views
peter-linz
peter-linz-edition4
theory-of-computation
pushdown-automata
0
votes
0
answers
60
Peter Linz Edition 4 Exercise 6.3 Question 4 (Page No. 173)
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 19, 2019
by
Naveen Kumar 3
95
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
Page:
« prev
1
2
3
4
5
6
7
...
20
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Recruitment of Scientific Officers in the Department of Atomic Energy 2023
GATE CSE 2023 Paper & Analysis - Memory Based
From GATE to Australia
DRDO Previous Year Papers
From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.6k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(649)
Exam Queries
(843)
Tier 1 Placement Questions
(17)
Job Queries
(75)
Projects
(9)
Unknown Category
(853)
Recent questions tagged peter-linz
Recent Blog Comments
+1
1200/1000 = 1.2
Aptitude- 1- there was a question, Like in a...
Suppose typing happens at 1 keystroke per second....
The algorithm for graph colouring was to pick...