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 contextfreelanguages
0
votes
1
answer
1
TIFR2020B2
Consider the following statements. The intersection of two contextfree languages is always contextfree The superset of a contextfree languages is never regular The subset of a decidable language is always decidable Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of all strings in which ... $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
asked
Feb 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

58
views
tifr2020
theoryofcomputation
contextfreelanguages
decidability
+1
vote
2
answers
2
ISRO202037
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
25.1k
points)

140
views
isro2020
theoryofcomputation
contextfreelanguages
easy
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 4 Question 31 (Page No. 212)
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

17
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
decidability
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 2 Question 58 (Page No. 160)
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its ... of $P's$ stack at that point cannot affect its subsequent behavior, so $P's$ subsequent behavior can depend only on $q$ and $x$.)
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
+2
votes
1
answer
5
Michael Sipser Edition 3 Exercise 2 Question 57 (Page No. 160)
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

33
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 2 Question 56 (Page No. 160)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ ... an accept state, it pretends that $c's$ are $b's$ in the input from that point on. What language would the modified $P$ accept?)
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 2 Question 53 (Page No. 159)
Show that the class of DCFLs is not closed under the following operations: Union Intersection Concatenation Star Reversal
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 2 Question 50 (Page No. 159)
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 2 Question 49 (Page No. 159)
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 2 Question 48 (Page No. 159)
Let $\Sigma = \{0,1\}$. Let $C_{1}$ be the language of all strings that contain a $1$ in their middle third. Let $C_{2}$ be the language of all strings that contain two $1s$ ... $C_{1}$ is a CFL. Show that $C_{2}$ is not a CFL.
asked
Oct 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

12
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
asked
Oct 12, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 2 Question 43 (Page No. 158)
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ ... a regular language is context free. What happens in part $(a)$ if $\Sigma$ contains three or more symbols? Prove your answer.
asked
Oct 12, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
13
Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.
asked
Oct 12, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

6
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 2 Question 41 (Page No. 158)
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$. Show that the class of CFLs is not closed under NOPREFIX. Show that the class of CFLs is not closed under NOEXTEND.
asked
Oct 12, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

9
views
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 2 Question 40 (Page No. 158)
Say that a language is prefixclosed if all prefixes of every string in the language are also in the language. Let $C$ be an infinite, prefixclosed, contextfree language. Show that $C$ contains an infinite regular subset.
asked
Oct 11, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

31
views
michaelsipser
theoryofcomputation
contextfreelanguages
prefixclosed
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 2 Question 39 (Page No. 158)
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of contextfree languages is not closed under shuffle.
asked
Oct 11, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
shuffle
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 2 Question 38 (Page No. 158)
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language $\text{{$w w = a_{1}b_{1} · · · a_{k}b_{k},$ where $a_{1} · · · a_{k} ... k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of contextfree languages is not closed under perfect shuffle.
asked
Oct 11, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

14
views
michaelsipser
theoryofcomputation
contextfreelanguages
perfectshuffle
+1
vote
1
answer
18
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, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.6k
points)

122
views
cmi2019
regularlanguages
contextfreelanguages
closureproperty
+1
vote
0
answers
19
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

93
views
ullman
theoryofcomputation
contextfreelanguages
pcp
descriptive
+1
vote
0
answers
20
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, 2019
in
Theory of Computation
by
Arjun
Veteran
(
434k
points)

158
views
ugcnetjune2019ii
contextfreelanguages
+1
vote
0
answers
21
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.5k
points)

96
views
peterlinz
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
+2
votes
0
answers
22
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.5k
points)

62
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
0
votes
1
answer
23
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.5k
points)

60
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
0
votes
0
answers
24
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.5k
points)

40
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
25
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.5k
points)

19
views
peterlinz
theoryofcomputation
contextfreelanguages
inherentlyambiguous
0
votes
0
answers
26
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.5k
points)

10
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
27
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.5k
points)

13
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
28
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.5k
points)

17
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
29
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.5k
points)

12
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
30
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.5k
points)

24
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
Page:
1
2
3
4
5
6
...
18
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
PSUs Recruitment
ISRO Recruitment
BARC Recruitment
GATE CSE: All NITs Admissions
GATE CSE: IIT Hyderabad Admissions
Follow @csegate
Recent questions tagged contextfreelanguages
Recent Blog Comments
Here is a poll on ISRO marks, you can say your...
They removed it,please create some poll or...
Did not find... post the link here
Please update your marks in gate overflow fb...
For CIL
50,834
questions
57,869
answers
199,518
comments
108,423
users