search
Log In

Recent questions tagged context-free-languages

1 vote
2 answers
1
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
asked Nov 20, 2020 in Theory of Computation jothee 96 views
1 vote
2 answers
2
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
asked Apr 1, 2020 in Theory of Computation Lakshman Patel RJIT 230 views
0 votes
1 answer
3
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
asked Apr 1, 2020 in Theory of Computation Lakshman Patel RJIT 137 views
1 vote
4 answers
4
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$
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 281 views
1 vote
3 answers
5
1 vote
3 answers
6
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
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 402 views
0 votes
3 answers
7
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 $L_{2}$ ... are context 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, 2020 in Theory of Computation jothee 322 views
1 vote
3 answers
8
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 all strings in which either ... $(2)$ Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
asked Feb 11, 2020 in Theory of Computation Lakshman Patel RJIT 332 views
1 vote
4 answers
9
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
asked Jan 13, 2020 in Theory of Computation Satbir 843 views
0 votes
0 answers
10
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 Lakshman Patel RJIT 141 views
0 votes
0 answers
11
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 stack below $x$, no matter what input ... that case, the contents 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 Lakshman Patel RJIT 43 views
0 votes
0 answers
13
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$ so that its input alphabet is $\{a, b, c\}$. When it first enters 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 Lakshman Patel RJIT 35 views
0 votes
0 answers
17
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 Lakshman Patel RJIT 54 views
0 votes
0 answers
19
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$ ... then the SCRAMBLE of 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 Lakshman Patel RJIT 37 views
0 votes
0 answers
20
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 Lakshman Patel RJIT 28 views
0 votes
0 answers
21
0 votes
0 answers
22
0 votes
0 answers
23
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 context-free languages is not closed under shuffle.
asked Oct 11, 2019 in Theory of Computation Lakshman Patel RJIT 63 views
0 votes
0 answers
24
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} ∈ A$ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of context-free languages is not closed under perfect shuffle.
asked Oct 11, 2019 in Theory of Computation Lakshman Patel RJIT 46 views
1 vote
1 answer
25
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 context-free context-free, but not regular both regular and context-free neither regular nor context-free
asked Sep 13, 2019 in Theory of Computation gatecse 273 views
1 vote
0 answers
26
2 votes
1 answer
27
How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite? By constructing redundant CFG G in CNF generating language $\underline{L}$ By constructing non-redundant CFG G in CNF generating language $L$ By constructing non-redundant CFG G in CNF ... $\wedge $ 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 Arjun 634 views
1 vote
0 answers
28
Determine whether or not the following languages are context-free. (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$}. (e)$L=$ {$a^nb^ja^kb^l : n ≤ k, j ≤ l$}. (f) $ 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 Naveen Kumar 3 248 views
...