# Questions tagged [context-free]

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

1,141 questions
Filter by
Sorted by
Tagged with
1answer
38 views

### Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
1answer
32 views

### Undecidability of checking whether all words can be generated from a context-free grammar?

I know it's undecidable, but how to prove it? Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate ...
1answer
49 views

### Is there an algorithm to overapproximate a context free grammar by a regular expression?

I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
2answers
57 views

### Convert this language to Context Free Grammar

I'm having trouble understanding how to convert this language to context free grammar. $\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$ Part im getting stuck on is how to deal with a and c, ...
2answers
60 views

### CFG for L {a^nb^m | n <= m+3}

I need a Context Free Grammar for this language. I could come up with this solution: S -> AB A -> aA | ε B -> bbbB | ε But, this grammar is clearly ...
2answers
94 views