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 contextfreelanguage
+1
vote
0
answers
1
Ullman (TOC) Edition 3 Exercise 9.5 Question 3 (Page No. 418  419)
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial ... Ogden's lemma to force equality in the lengths of certain substrings as in the hint to Exercise $7.2.5(b)$.
asked
Jul 26
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
46.5k
points)

45
views
ullman
theoryofcomputation
contextfreelanguage
pcp
descriptive
+1
vote
0
answers
2
UGCNETJune2019II77
How can the decision algorithm be constructed for deciding whether contextfree language $L$ is finite? By constructing redundant CFG G in CNF generating language $\underline{L}$ By constructing nonredundant CFG G in CNF generating language $L$ By constructing nonredundant CFG ... stands for null) Which of the following is correct? a only b only c only None of a, b and c
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
418k
points)

41
views
ugcnetjune2019ii
contextfreelanguage
0
votes
0
answers
3
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

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

34
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
1
answer
5
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
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

43
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
+1
vote
1
answer
6
Theory of Computation: Context Free Languages
Hi, I am having a doubt understanding the result of CFL  Regular: Here's my approach: CFL  Regular = CFL INTERSECTION Regular' = CFL INTERSECTION Regular = CFL Suppose some CFL L1= {a^n b^n  n>=1} and some Regular R1= (a+b)* ... to say CFL  Regular = Regular or CFL  Regular = CFL ? If both are separate options, which one should I go for? Thanks
asked
Jun 9
in
Theory of Computation
by
DukeThunders
(
39
points)

42
views
theoryofcomputation
contextfreelanguage
selfdoubt
0
votes
1
answer
7
ACE Academy: Recognition of CFG
$L1 =\left \{ a^{m} b^{n} c^{p}  \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p}  \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not contextfree $(d)$ Both are not contextfree
asked
May 23
in
Theory of Computation
by
Hirak
Active
(
3.4k
points)

59
views
cfg
contextfreelanguage
dcfl
0
votes
1
answer
8
self doubt: TOC
is union of regular language and context free language always regular?
asked
May 22
in
Theory of Computation
by
Hirak
Active
(
3.4k
points)

45
views
theoryofcomputation
regularlanguages
contextfreelanguage
+1
vote
0
answers
9
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
(
399
points)

113
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
10
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
(
14k
points)

25
views
peterlinz
contextfreegrammars
contextfreelanguage
0
votes
0
answers
11
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)

40
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
12
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)

40
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
13
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)

21
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
14
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)

25
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
15
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)

7
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
16
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)

27
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
17
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)

14
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
18
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)

6
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
19
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)

23
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
20
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)

21
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
21
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)

26
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
22
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)

23
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
23
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)

13
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
0
answers
24
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
(
14k
points)

3
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
25
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
(
14k
points)

3
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
26
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
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
27
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
(
14k
points)

12
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
28
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
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
29
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
(
14k
points)

10
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
30
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
(
14k
points)

12
views
peterlinz
theoryofcomputation
contextfreegrammars
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
GATE 2020 Application Form Opened!
My GATE Preparation Journey
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Follow @csegate
Recent questions tagged contextfreelanguage
Recent Blog Comments
will pdfs be uploaded ?
6th...
Sir
4th...
49,984
questions
55,138
answers
190,495
comments
85,159
users