The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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 contextfreelanguage
+1
vote
0
answers
1
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
asked
May 10
in
Theory of Computation
by
logan1x
(
235
points)

68
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aSAB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?
asked
Apr 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

21
views
peterlinz
contextfreegrammars
contextfreelanguage
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

26
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree $L = \{a^nb^m:\text{n is prime or m is prime}\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

24
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree $L = \{a^nb^m: \text{n and m are both prime}\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

17
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

24
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

6
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

12
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

13
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L=\{a^nb^jc^k : k>n,k>j\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

5
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{a^nb^jc^k:k=jn\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

22
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 8.1 Question 7(b) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{a^nb^j: n\geq(j1)^3\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

19
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 8.1 Question 7(a) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{a^nb^j : n\leq j^2\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

23
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 8.1 Question 6 (Page No. 212)
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

22
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

12
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 5.1 Question 26 (Page No. 135)
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

3
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 5.1 Question 25 (Page No. 135)
Prove that if $G$ is a contextfree grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a derivation tree.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

3
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 5.1 Question 19 (Page No. 134)
Show a derivation tree for the string $aabbbb$ with the grammar $S\rightarrow AB\lambda,$ $A\rightarrow aB,$ $B\rightarrow Sb.$ Give a verbal description of the language generated by this grammar.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 5.1 Question 18 (Page No. 134)
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is contextfree.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

10
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 5.1 Question 17 (Page No. 134)
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is contextfree.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

3
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 5.1 Question 16 (Page No. 134)
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is contextfree.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

8
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 5.1 Question 15 (Page No. 134)
Show that the following language is contextfree. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,u=w=2$}.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

9
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 5.1 Question 14 (Page No. 134)
Let $L_1$ be the language $L_1 =$ {$a^nb^mc^k : n = m$ or $m ≤ k$} and $L_2$ the language $L_2 =$ {$a^nb^mc^k : n + 2m = k$}. Show that $L_1 ∪ L_2$ is a contextfree language.
asked
Apr 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

20
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 5.1 Question 9 (Page No. 134)
Show that $L =$ {$w ∈$ {$a,b,c$}$^* : w = 3n_a(w)$} is a contextfree language.
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

13
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
25
Peter Linz Edition 4 Exercise 5.1 Question 8 (Page No. 134)
Find contextfree grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$). (a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}. (b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}. (c) $L =$ {$a^nb^mc^k : k = n + m$}. (d) $L =$ ... $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

12
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 5.1 Question 7 (Page No. 133)
Find contextfree grammars for the following languages (with $n ≥ 0, m ≥ 0$). (a) $L =$ {$a^nb^m : n ≤ m + 3$}. (b) $L =$ {$a^nb^m : n ≠ m − 1$ ... $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
11.7k
points)

12
views
peterlinz
theoryofcomputation
contextfreelanguage
contextfreegrammars
0
votes
1
answer
27
CFG Doubt
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in w how to approach this?
asked
Mar 7
in
Theory of Computation
by
aditi19
Active
(
3.4k
points)

119
views
contextfreelanguage
theoryofcomputation
contextfreegrammars
0
votes
1
answer
28
CFG Doubt
S>A  B A→ ε B>aBb B>b what is the complement of the language of this grammar?
asked
Mar 2
in
Theory of Computation
by
aditi19
Active
(
3.4k
points)

113
views
contextfreelanguage
theoryofcomputation
contextfreegrammars
0
votes
1
answer
29
Peter Linz Edition 4 Exercise 5.1 Question 13.a (Page No. 134)
L={$a^nb^n  n\geq 0$} please show how $L^2$ is CFL
asked
Mar 1
in
Theory of Computation
by
aditi19
Active
(
3.4k
points)

115
views
theoryofcomputation
peterlinz
contextfreelanguage
contextfreegrammars
0
votes
3
answers
30
GATE201931
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT contextfree? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
399k
points)

1.7k
views
gate2019
theoryofcomputation
contextfreelanguage
Page:
1
2
3
4
5
6
...
13
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
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
Follow @csegate
Recent questions tagged contextfreelanguage
Recent Blog Comments
No restrictions. I did use vector at many...
@kunal If you were in Software Lab 2, then you...
No such thing was mentioned to us. There was no...
C and C++ were allowed (Compiler was g++ ). Only...
49,403
questions
53,576
answers
185,762
comments
70,852
users