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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged peterlinz
+1
vote
1
answer
1
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).
asked
May 26
in
Theory of Computation
by
suraj prasad shaw
(
47
points)

33
views
peterlinz
theoryofcomputation
0
votes
0
answers
2
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

31
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
3
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

25
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
4
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

22
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
5
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

26
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
6
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

15
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
7
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

17
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
8
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

36
views
peterlinz
theoryofcomputation
pushdownautomata
npda
0
votes
0
answers
9
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

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

30
views
peterlinz
theoryofcomputation
pushdownautomata
0
votes
0
answers
11
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 → aSbb$.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

19
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BBa,$ $B\rightarrow ABb.$
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

25
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 6.3 Question 1 (Page No. 172)
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in the language generated by the grammar with productions $S\rightarrow AB,$ $A\rightarrow BBa,$ $B\rightarrow ABb.$
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Twostandard form is general; for any contextfree grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in twostandard form.” Prove this.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

22
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A contextfree grammar is said to be in twostandard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ $A\rightarrow aB,$ $A\rightarrow a,$ where $A, B, C ∈ V$ and $a ∈ T$. Convert the grammar ... $S\rightarrow aSA,$ $A\rightarrow bABC,$ $B\rightarrow b,$ $C\rightarrow aBC$ into twostandard form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

2
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

24
views
peterlinz
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 6.2 Question 13 (Page No. 170)
Convert the grammar $S\rightarrow ABba,$ $A\rightarrow aaAB,$ $B\rightarrow bAb$ into Greibach normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

7
views
peterlinz
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow abaSaaS$ into Greibach normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

14
views
peterlinz
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSbab$
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

16
views
peterlinz
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 6.2 Question 10 (Page No. 170)
Convert the grammar $S\rightarrow aSbbSaab$ into Greibach normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 6.2 Question 9 (Page No. 170)
Show that for every contextfree grammar $G = (V, T, S, P)$ there is an equivalent one in which all productions have the form $A → aBC,$ or $A → λ,$ where $a∈Σ$ $\cup$ {$\lambda$} , $A,B,C∈V$.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

13
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 6.2 Question 8 (Page No. 169)
A linear language is one for which there exists a linear grammar [A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable. Clearly, a regular grammar is always ... $A\rightarrow a,$ where $a∈ T$ , $A, B∈ V,$ such that $L = L (G)$.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

22
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 6.2 Question 7 (Page No. 169)
Draw the dependency graph for the grammar in Exercise 4.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

14
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
25
Peter Linz Edition 4 Exercise 6.2 Question 6 (Page No. 169)
Let $G = (V, T, S, P)$ be any contextfree grammar without any $λ$productions or unitproductions. Let $k$ be the maximum number of symbols on the right of any production in $P$. Show that there is an equivalent grammar in Chomsky normal form with no more than $(k1)P+T$ production rules.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

19
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 6.2 Question 5 (Page No. 169)
Convert the grammar with productions $S\rightarrow ABaB,$ $A\rightarrow aab\lambda,$ $B\rightarrow bbA$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

18
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 6.2 Question 4 (Page No. 169)
Transform the grammar with productions $S\rightarrow abAB,$ $A\rightarrow bAB\lambda,$ $B\rightarrow BAaA\lambda$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 6.2 Question 3 (Page No. 169)
Transform the grammar $S\rightarrow aSaAA, A\rightarrow abAb$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

15
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 6.2 Question 2 (Page No. 169)
Convert the grammar $S\rightarrow aSbab$ into Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

22
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 6.2 Question 1 (Page No. 169)
Provide the details of the proof of Theorem 6.6. Theorem 6.6 Any contextfree grammar $G = (V, T, S, P)$ with $λ ∉ L (G)$ has an equivalent grammar $\widehat G=(\widehat V,\widehat T,S,\widehat P)$ in Chomsky normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

18
views
peterlinz
theoryofcomputation
contextfreegrammars
Page:
1
2
3
4
5
6
...
18
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
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Thanks GO!!
IIIT Hyerabad Interview Expeience  MS by Research in CSE
Follow @csegate
Recent questions tagged peterlinz
Recent Blog Comments
My rank in gate was a disaster...2111 rank and...
Sir whats you rank ?
Ok,Thank you for replying!
By a good profile I mean having academic...
Thank you sir..
49,532
questions
54,132
answers
187,336
comments
71,056
users