The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
2
answers
1
UGCNETJan2017III: 23
Given the following two languages : $L_{1}= \{a^{n}b^{n}, \mid n\geq 0,n \neq 100 \}$ $L_{2}= \{w \in \{a,b,c \} ^{\ast} \mid n_{a}(w)=n_{b}(w)=n_{c}(w) \}$ Which of the following options is correct? Both $L_{1}$ and ... free language $L_{1}$ is context free language, $L_{2}$ is not context free language $L_{1}$ is not context free language, $L_{2}$ is context free language
asked
Mar 24
in
Theory of Computation
by
jothee

68
views
ugcnetjan2017iii
theoryofcomputation
contextfreelanguages
+1
vote
2
answers
2
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

145
views
tifr2020
theoryofcomputation
contextfreelanguages
decidability
+1
vote
3
answers
3
ISRO202037
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
asked
Jan 14
in
Theory of Computation
by
Satbir

263
views
isro2020
theoryofcomputation
contextfreelanguages
easy
0
votes
0
answers
4
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 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

67
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
decidability
proof
0
votes
0
answers
5
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

17
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
+2
votes
1
answer
6
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

50
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
7
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

15
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
8
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

26
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
9
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

26
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
10
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

34
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
11
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

22
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
12
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 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

22
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
13
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 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

17
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
14
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 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
15
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 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

23
views
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
0
answers
16
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

39
views
michaelsipser
theoryofcomputation
contextfreelanguages
prefixclosed
0
votes
0
answers
17
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

37
views
michaelsipser
theoryofcomputation
contextfreelanguages
shuffle
0
votes
0
answers
18
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

22
views
michaelsipser
theoryofcomputation
contextfreelanguages
perfectshuffle
+1
vote
1
answer
19
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 14, 2019
in
Theory of Computation
by
gatecse

171
views
cmi2019
regularlanguages
contextfreelanguages
closureproperty
+1
vote
0
answers
20
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 27, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

113
views
ullman
theoryofcomputation
contextfreelanguages
pcp
descriptive
+2
votes
0
answers
21
UGCNETJune2019II: 77
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 ... stands for null) Which of the following is correct? a only b only c only None of a, b and c
asked
Jul 3, 2019
in
Theory of Computation
by
Arjun

338
views
ugcnetjune2019ii
contextfreelanguages
+1
vote
0
answers
22
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

139
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
+2
votes
0
answers
23
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

91
views
peterlinz
peterlinzedition4
theoryofcomputation
pumpinglemma
contextfreelanguages
0
votes
1
answer
24
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

85
views
peterlinz
peterlinzedition4
theoryofcomputation
pumpinglemma
contextfreelanguages
0
votes
0
answers
25
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

67
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
26
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

30
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreelanguages
inherentlyambiguous
0
votes
0
answers
27
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

24
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
28
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

23
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
29
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

32
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
30
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

23
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged contextfreelanguages
Recent Blog Comments
Q1. I don't know any trick or method, I usually...
Yeah, Now it's on.
Can you check now?
Even I filled NIELIT form which had similar...
Today's test will be late  either midnight or...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,571
answers
201,973
comments
95,387
users