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
0
votes
0
answers
1
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
(
414k
points)

21
views
ugcnetjune2019ii
contextfreelanguage
0
votes
0
answers
2
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)

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

27
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
1
answer
4
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)

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

40
views
theoryofcomputation
contextfreelanguage
selfdoubt
0
votes
1
answer
6
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.3k
points)

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

44
views
theoryofcomputation
regularlanguages
contextfreelanguage
+1
vote
0
answers
8
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)

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

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

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

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

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

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

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

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

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

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

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

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

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

13
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
0
answers
23
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
24
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
25
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
26
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)

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

23
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
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Follow @csegate
Recent questions tagged contextfreelanguage
Recent Blog Comments
yeah me too. I did not get the address...
@arjun sir is it possible to reconfirm address...
@Arjun, Sir the address confirmation email I...
All the tests scheduled to be added here are...
49,814
questions
54,518
answers
188,351
comments
75,290
users