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 peterlinz
+1
vote
0
answers
1
Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
Determine whether or not the following languages are contextfree. (a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*} (b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}. (C) $L=$ {$a^nb^ja^jb^n : n ≥ 0, j ≥ 0$}. (d) $L=$ {$a^nb^ja^kb^l : n + j ≤ k + l$ ... $ L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

82
views
peterlinz
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
+2
votes
0
answers
2
Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} contextfree?
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

54
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
0
votes
1
answer
3
Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not contextfree.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

56
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}. (i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} . (ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} . (iii) $L=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

33
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
5
Peter Linz Edition 4 Exercise 7.4 Question 8 (Page No. 204)
Let G be a contextfree grammar in Greibach normal form. Describe an algorithm which, for any given k, determines whether or not G is an LL (k) grammar.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

13
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 7.4 Question 7 (Page No. 204)
Show that a deterministic contextfree language is never inherently ambiguous.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

17
views
peterlinz
theoryofcomputation
contextfreelanguages
inherentlyambiguous
0
votes
0
answers
7
Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic contextfree language.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

9
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
9
Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

12
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
11
Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

20
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 7.4 Question 1 (Page No. 204)
Show that the grammar $S_0\rightarrow aSbS,S\rightarrow aSbS\lambda$ is an LL grammar and that it is equivalent to the grammar $S\rightarrow SSaSbab$.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 7.3 Question 18 (Page No. 200)
Give an example of a deterministic contextfree language whose reverse is not deterministic.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

49
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 7.3 Question 17 (Page No. 200)
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

18
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
15
Peter Linz Edition 4 Exercise 7.3 Question 16 (Page No. 200)
Show that if $L_1$ is deterministic contextfree and $L_2$ is regular, then the language $L_1 ∪ L_2$ is deterministic contextfree.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

23
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
16
Peter Linz Edition 4 Exercise 7.3 Question 15 (Page No. 200)
Show that every regular language is a deterministic contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

18
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 7.3 Question 11 (Page No. 200)
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

12
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
18
Peter Linz Edition 4 Exercise 7.3 Question 10 (Page No. 200)
While the language in Exercise 9 is deterministic, the closely related language $L =$ {$ww^R : w ∈${$a,b$}$^*$} is known to be nondeterministic. Give arguments that make this statement plausible.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

19
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
19
Peter Linz Edition 4 Exercise 7.3 Question 9 (Page No. 200)
Is the language {$wcw^R : w ∈ ${$a, b$}$^*$} deterministic?
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

37
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 7.3 Question 8 (Page No. 200)
Is the language $L =$ {$a^nb^m : n = m$ or $n = m + 2$} deterministic?
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

26
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 7.3 Question 7 (Page No. 200)
Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k$}.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

38
views
peterlinz
theoryofcomputation
contextfreelanguages
+1
vote
1
answer
22
Peter Linz Edition 4 Exercise 7.3 Question 6 (Page No. 200)
For the language $L =$ {$a^nb^{2n} : n ≥ 0$}, show that $L^*$ is a deterministic contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

16
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
23
Peter Linz Edition 4 Exercise 7.3 Question 4 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$a$} deterministic?
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

28
views
peterlinz
theoryofcomputation
contextfreelanguages
+1
vote
1
answer
24
Peter Linz Edition 4 Exercise 7.3 Question 3 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

22
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
25
Peter Linz Edition 4 Exercise 7.3 Question 2 (Page No. 200)
Show that $L =$ {$a^nb^m : m ≥ n + 2$} is deterministic.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

8
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 7.3 Question 1 (Page No. 200)
Show that $L =$ {$a^nb^{2n} : n ≥ 0$} is a deterministic contextfree language.
asked
Jun 23, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

5
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
27
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
28
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
29
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
30
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)

12
views
peterlinz
theoryofcomputation
pushdownautomata
npda
Page:
1
2
3
4
5
6
...
20
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
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged peterlinz
Recent Blog Comments
Q42 C option is correct for C set as it is an...
@ smsubham The SQL query question No...
Are SQL query and that case 1, case 2 answer in...
@ Debapaul Correct answer should be...
Question No. 42 (BIG ENDIAN QUESTION) in Set 'C'...
50,737
questions
57,271
answers
198,135
comments
104,777
users