# Questions tagged [context-free]

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

1,189 questions
Filter by
Sorted by
Tagged with
104 views

### How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

I know that CFG for $$\{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is $$S\rightarrow ab/abb/aSb/aSbb$$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
28 views

### Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}

I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help Thanks in Advance!
88 views

### Leo's deterministic reduction for Earley Parsing

I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows: ...
19 views

### Is the set of context free grammars that generate no words in co-RE? [duplicate]

Is the $\{ \langle G \rangle \mid L(G) = \emptyset \}$ recursively enumerable or co-recursively enumerable?
35 views

### Efficiency/Redundancy in Chomsky normal form

I have a context-free grammar with the following production rules, $S$ being the start symbol: \begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*} Is this in Chomsky normal ...
48 views

### What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
82 views

### How to give a context free grammar for any given language ie: a^n (ba)^m a^n

i am trying to understand Context free grammar and generate a CFG for any given language. when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow ...
130 views

### Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$ So far, this is the solution that I have been able to come up with, though I am not sure how accurate ...
71 views

### Need help understanding what co-recursively enumerable means

Lets say I have a set: $L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
45 views

### Is the set of context free grammars that generate all words in co-RE?

Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
30 views

### Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language?

My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, ...
33 views

### Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]

I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
52 views

### if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
253 views

### Does every infinite context free language contain an infinite regular subset?

Can someone explain to me if this is true or not?
62 views

### Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free?

Consider the following languages: \begin{align*} L_1 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0 \}, \\ L_2 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0, \; p \neq r \}. \end{align*} Which one of ...
386 views

### Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
176 views

### How prefix property of language affects the PDA

I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this ...
377 views

### Prove complement a^nb^nc^n is contextfree

So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}. In other words, any combinations of a,b and c where we dont have an equal number ...
85 views

### Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
73 views

50 views

### Context-Free Grammar from this language

I'm having difficulties with an exercise in a theoretical CS class. The problem is: let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
59 views

### unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
First, we state here a theorem that is well-known in computability theory: $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$ And, the standard proof is using pumping lemma. At ...
### Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?
Our problem is: Given a context-free grammar $G$ and a string $x$, decide whether $x\in L(G)$. Is this language itself context-free?