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 contextfreelanguage
+1
vote
1
answer
1
CMI2019A1
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not contextfree contextfree, but not regular both regular and contextfree neither regular nor contextfree
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.6k
points)

88
views
cmi2019
regularlanguages
contextfreelanguage
closureproperty
+1
vote
0
answers
2
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
Veteran
(
53.4k
points)

82
views
ullman
theoryofcomputation
contextfreelanguage
pcp
descriptive
+1
vote
0
answers
3
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
(
423k
points)

92
views
ugcnetjune2019ii
contextfreelanguage
+1
vote
0
answers
4
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
(
15.1k
points)

71
views
peterlinz
theoryofcomputation
contextfreelanguage
pumpinglemma
proof
+1
vote
0
answers
5
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
(
15.1k
points)

48
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
1
answer
6
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
(
15.1k
points)

51
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
+1
vote
1
answer
7
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)

50
views
theoryofcomputation
contextfreelanguage
selfdoubt
0
votes
1
answer
8
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.5k
points)

74
views
cfg
contextfreelanguage
dcfl
0
votes
1
answer
9
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.5k
points)

52
views
theoryofcomputation
regularlanguages
contextfreelanguage
+1
vote
0
answers
10
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
Junior
(
803
points)

119
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
11
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
(
15.1k
points)

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

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

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

21
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
15
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
(
11.3k
points)

25
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
16
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
(
11.3k
points)

7
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
17
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
(
11.3k
points)

29
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
18
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
(
11.3k
points)

18
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
19
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
(
11.3k
points)

6
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
20
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
(
11.3k
points)

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

21
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
+1
vote
0
answers
22
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
(
11.3k
points)

28
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
23
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
(
11.3k
points)

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

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

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

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

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

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

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

11
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
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Follow @csegate
Recent questions tagged contextfreelanguage
Recent Blog Comments
still it's usefull for practice purpose and...
@Satbir Its a valuable info..Thanks
It is the 2019 question paper given as a mock...
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
50,650
questions
56,185
answers
193,937
comments
94,684
users