# Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

1,188 questions
Filter by
Sorted by
Tagged with
19k views

### How to take complement of a language?

I'm stuck on this question about context-free languages and was hoping for some clarification. $\qquad L = \{a^i b^j c^k \mid i=j, i=k\}$ is not context-free. Show that its complement is ...
1k views

### Is {xyx | |x|≥1} context-free?

Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free? If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping ...
214 views

### Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free

How can I prove that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not a context free language? I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ ...
2k views

### prove no DPDA accepts language of even-lengthed palindromes

How do you prove that the language of even-lengthed palindromes, i.e., $L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton? Is ...
1k views

### Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

Is the following language context free? $$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\}$$ As pointed out by sdcvvc, a word in this language can also be ...
718 views

### Prove that context free languages are not closed under swapping prefixes and suffixes

Prove that context free languages aren't closed under this operation: $A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \}$ Obviously, we need to find a context free language $L$ such that $A(L)$ ...
3k views

### Converting CFG to PDA

I have the following CFG, $S \rightarrow CB$ $C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$ $B \rightarrow AB \text{ }|\text{ } \varepsilon$ $A \rightarrow a\text{ }|\text{ }b$ ...
1k views

### Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \}$ context free?

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \}$ context free ? If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \}$ is ...
2k views

### Is the intersection of two context free languages recursively enumerable?

I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable. I could not, however, find a citation for this quotation (and ...
61 views

### Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free
This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not ...
Can someone help with this: $L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$ I'm trying to write a grammar for this language? I don't know how to do this. I tried this: \$S \rightarrow aaAb \...