Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged context-free-language
1
votes
0
answers
61
Self Doubt about Construction of CFG
I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j > 0\}$, this is what I came up with: $ S \rightarrow A \ | \ B $ $A \rightarrow 0A1 \ |\ A1 \ |\ 011$ ... strings that we can have: s = {011, 00111, 001, 00011, ...} and it worked. So, my question is, is this correct CFG for this particular L?
I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j 0\}$, this is what I came up with:$ S \rightarrow A \ | \ B $$A \righ...
HenryAsks21
308
views
HenryAsks21
asked
Apr 30, 2022
Theory of Computation
theory-of-computation
context-free-language
+
–
24
votes
2
answers
62
GATE CSE 2022 | Question: 37
Consider the following languages: $L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$ $L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}$ Note that $w^{R}$ is the reversal of the string $w.$ Which of the following is/are ... $L_{2}$ are context-free. $L_{1}$ is regular and $L_{2}$ is context-free. $L_{1}$ and $L_{2}$ are context-free but not regular.
Consider the following languages:$L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$$L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| 0 \}$Note that $w^{R}$ is the reve...
Arjun
7.0k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
identify-class-language
context-free-language
multiple-selects
2-marks
+
–
20
votes
2
answers
63
GATE CSE 2022 | Question: 38
Consider the following languages: $L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ $L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$ $L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$ Which of the following statements is/are $\text{FALSE}?$ ... $L_{2}$ is context-free. $L_{2}, L_{3}$ and $L_{2} \cap L_{3}$ all are context-free. Neither $L_{1}$ nor its complement is context-free.
Consider the following languages:$L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$$L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$$L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$Which ...
Arjun
11.0k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
context-free-language
multiple-selects
2-marks
+
–
1
votes
2
answers
64
DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.
Is the following language a DCFL? Please explain your reasoning.
atulcse
676
views
atulcse
asked
Jan 21, 2022
Theory of Computation
theory-of-computation
dcfl
context-free-language
pushdown-automata
+
–
0
votes
1
answer
65
parse tree - context-free grammars - TOC
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
atulcse
829
views
atulcse
asked
Jan 21, 2022
Theory of Computation
context-free-language
theory-of-computation
compiler-design
finite-automata
+
–
0
votes
2
answers
66
made easy test series - parsing - context-free grammar
Consider the following context-free grammar: Find the number of unique productions in {Goto (A → D.BC, B) U Goto (A → .DBC, D)}
Consider the following context-free grammar:Find the number of unique productions in {Goto (A → D.BC, B) U Goto (A → .DBC, D)}
atulcse
861
views
atulcse
asked
Jan 16, 2022
Compiler Design
context-free-language
context-free-grammar
parsing
made-easy-test-series
+
–
3
votes
2
answers
67
#Gate CS Applied Course Mock Test
Is this Language a CFL? If yes, Can you please explain the implementation.
Is this Language a CFL?If yes, Can you please explain the implementation.
Rajesh Reddy
574
views
Rajesh Reddy
asked
Jan 3, 2022
Theory of Computation
theory-of-computation
context-free-language
context-free-grammar
+
–
2
votes
3
answers
68
regular and cfl
if L1 and L2 are not regular language then L1 union L2 is not regular. this statement is true or false? my approach is::: true let suppose L1= a^n b^n AND L2= a^k b^k both are cfl but if we do union then that also be cfl and what happened if union is replaced by concatenation L1 . L2
if L1 and L2 are not regular language then L1 union L2 is not regular.this statement is true or false?my approach is:::true let suppose L1= a^n b^n AND L2= a^k b^kbot...
jugnu1337
1.1k
views
jugnu1337
asked
Dec 23, 2021
Theory of Computation
context-free-language
finite-automata
theory-of-computation
+
–
3
votes
3
answers
69
#selfDoubt
complement of CFL can never be CFL. please explain if the above statement is true of false?
complement of CFL can never be CFL.please explain if the above statement is true of false?
BHOJARAM
823
views
BHOJARAM
asked
Dec 13, 2021
Theory of Computation
theory-of-computation
context-free-language
normal
self-doubt
+
–
0
votes
1
answer
70
Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.
let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...
UltraRadiantX
450
views
UltraRadiantX
asked
Oct 9, 2021
Theory of Computation
theory-of-computation
context-free-language
context-sensitive
+
–
1
votes
1
answer
71
Applied Test Series
The language accepted by the given PDA is
The language accepted by the given PDA is
LRU
280
views
LRU
asked
Oct 3, 2021
Theory of Computation
theory-of-computation
context-free-language
npda
test-series
+
–
1
votes
2
answers
72
can someone share the approach for the following que
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not. Can someone share the approach for second part.
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not.Can someone share the approach for second part.
mk_007
253
views
mk_007
asked
Oct 2, 2021
Theory of Computation
context-free-language
context-free-grammar
ambiguous
+
–
2
votes
3
answers
73
UGC NET CSE | June 2016 | Part 3 | Question: 56
Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct? $\overline L$ is context free and $L^k$ is not context free for any $k\ge1$ $\overline L$ is not context free and $L^k$ ... $L^k$ for any $k\ge1$ are context free Both $\overline L$ and $L^k$ for any $k\ge1$ are not context free
Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct?$\overline L$ is context free and $L^k$ is not context free for any $k\ge1$$\overl...
soujanyareddy13
619
views
soujanyareddy13
asked
May 10, 2021
Theory of Computation
ugcnetcse-june2016-paper3
context-free-language
+
–
1
votes
1
answer
74
TIFR CSE 2021 | Part B | Question: 5
For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the following sentences. $\overline{L}$ and $L^{\ast}$ are both context-free. $\overline{L}$ is not ... ? Both (i) and (iii) Only (i) Only (iii) Only (ii) None of the above
For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the followi...
soujanyareddy13
642
views
soujanyareddy13
asked
Mar 25, 2021
Theory of Computation
tifr2021
theory-of-computation
context-free-language
+
–
27
votes
2
answers
75
GATE CSE 2021 Set 2 | Question: 41
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$.Which of the following languages is/are context-free?$\{ wxw^Rx^R \...
Arjun
7.1k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set2
multiple-selects
theory-of-computation
context-free-language
2-marks
+
–
11
votes
3
answers
76
GATE CSE 2021 Set 1 | Question: 1
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free?$L_1 \cap L_2...
Arjun
7.4k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set1
context-free-language
theory-of-computation
1-mark
+
–
2
votes
2
answers
77
UGC NET CSE | October 2020 | Part 2 | Question: 29
Which of the following statements is true? The union of two context free languages is context free The intersection of two context free languages is context free The complement of a context free language is context free If a language is context free, it can always be accepted by a deterministic pushdown automaton
Which of the following statements is true?The union of two context free languages is context freeThe intersection of two context free languages is context freeThe complem...
go_editor
4.0k
views
go_editor
asked
Nov 20, 2020
Theory of Computation
ugcnetcse-oct2020-paper2
theory-of-computation
context-free-language
+
–
1
votes
1
answer
78
NIELIT 2017 OCT Scientific Assistant A (IT) - Section C: 9
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ Only $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
Which of the following definitions generates the same languages as $L,$ where$L = \{x^{n}y^{n},n \geq 1\}$$E \rightarrow xEy \mid xy$$xy \mid x^{+}xyy^{+}$$x^{+}y^{+}$ $(...
admin
604
views
admin
asked
Apr 1, 2020
Theory of Computation
nielit2017oct-assistanta-it
theory-of-computation
context-free-language
+
–
1
votes
2
answers
79
NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 31
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
Which of the following definitions generates the same languages as $L,$ where$L = \{x^{n}y^{n},n \geq 1\}$$E \rightarrow xEy \mid xy$$xy \mid x^{+}xyy^{+}$$x^{+}y^{+}$ $(...
admin
608
views
admin
asked
Apr 1, 2020
Theory of Computation
nielit2017oct-assistanta-cs
theory-of-computation
context-free-language
+
–
2
votes
4
answers
80
NIELIT 2016 MAR Scientist B - Section C: 26
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language? $L_1L_2$ $L_1\cap L_2$ $L_1\cap R$ $L_1\cup L_2$
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language?$L_1L_2$$L_1\cap L_2$...
admin
903
views
admin
asked
Mar 31, 2020
Theory of Computation
nielit2016mar-scientistb
theory-of-computation
context-free-language
+
–
2
votes
3
answers
81
NIELIT 2016 DEC Scientist B (CS) - Section B: 3
If $L1$ is CFL and $L2$ is regular language which of the following is false? $L1-L2$ is not Context free $L1$ intersection $L2$ is Context free $\sim L1$ is Context free Both (A) and (C)
If $L1$ is CFL and $L2$ is regular language which of the following is false?$L1-L2$ is not Context free$L1$ intersection $L2$ is Context free$\sim L1$ is Context freeBoth...
admin
744
views
admin
asked
Mar 31, 2020
Theory of Computation
nielit2016dec-scientistb-cs
theory-of-computation
context-free-language
+
–
2
votes
3
answers
82
NIELIT 2017 DEC Scientist B - Section B: 56
Which of the following statement is true? Deterministic context free language are closed under complement. Deterministic context free language are not closed under Union. Deterministic context free language are closed under intersection with regular set. All of the options
Which of the following statement is true?Deterministic context free language are closed under complement.Deterministic context free language are not closed under Union.De...
admin
1.5k
views
admin
asked
Mar 30, 2020
Theory of Computation
nielit2017dec-scientistb
theory-of-computation
identify-class-language
context-free-language
+
–
3
votes
4
answers
83
TIFR CSE 2020 | Part B | Question: 2
Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free 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 ... Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
Consider the following statements.The intersection of two context-free languages is always context-freeThe super-set of a context-free languages is never regularThe subse...
admin
1.5k
views
admin
asked
Feb 10, 2020
Theory of Computation
tifr2020
theory-of-computation
context-free-language
decidability
+
–
2
votes
4
answers
84
ISRO2020-37
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
Context free languages are closed underunion, intersectionunion, kleene closureintersection, complementcomplement, kleene closure
Satbir
2.7k
views
Satbir
asked
Jan 13, 2020
Theory of Computation
isro-2020
theory-of-computation
context-free-language
easy
+
–
1
votes
0
answers
85
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.
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 te...
admin
449
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
decidability
proof
+
–
0
votes
0
answers
86
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$.)
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 ...
admin
192
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
2
votes
1
answer
87
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.
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.
admin
309
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
Page:
« prev
1
2
3
4
5
6
7
8
...
21
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register