search
Log In

Recent questions tagged context-free-languages

1 vote
2 answers
1
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 in Theory of Computation Lakshman Patel RJIT 150 views
0 votes
1 answer
2
1 vote
4 answers
3
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 in Theory of Computation Lakshman Patel RJIT 199 views
2 votes
5 answers
4
If $L$ be a language recognizable by a finite automaton, then language from $\{L\} = \{w$ such that $w$ is a prefix of $v$ where $v\in L\}$, is a regular language. context-free language. context-sensitive language. recursive enumeration language
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 207 views
1 vote
3 answers
5
0 votes
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 in Theory of Computation Lakshman Patel RJIT 189 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 in Theory of Computation jothee 207 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 in Theory of Computation Lakshman Patel RJIT 200 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 in Theory of Computation Satbir 448 views
0 votes
0 answers
10
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 29 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 24 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 37 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 30 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 22 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 46 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 36 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 237 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 532 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 192 views
...