# Questions tagged [context-free]

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

1,681 questions
Filter by
Sorted by
Tagged with
239 views

### Intuition for Sipser's proof of PDA to CFG

I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two. He splits the proof (...
• 33
90 views

• 101
46 views

### Pumping lemma for context-free languages: Importance of length restriction

(from 'An Introduction to Formal Languages and Automata' by Peter Linz) What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction ...
• 89
119 views

### What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
90 views

### How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
1 vote
277 views

46 views

### Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$

I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. ...
• 453
76 views

### Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?

$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$. ...
266 views

• 167