# Questions tagged [context-free]

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

1,733 questions
Filter by
Sorted by
Tagged with
180 views

### Understanding a bound for derivation length of any string in Pumping lemma for context-free languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz: Let $L$ be an ...
• 134
1 vote
54 views

### Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
1 vote
50 views

### Alternative solution for the Dangling Else Problem

I understand that one of the ways to solve the Dangling Else Problem is by imposing innermost binding. So, we have to transform the following ambiguous grammar: ...
Let's say we want to construct the PDA for the following language: $$L_4 = \{w_1bw_2 | w_1, w_2 \in \{a,b,c \}^* \ and \ (\#ab\in w_1) = (2 \times \#c \in w_2)\}$$ Let's consider the following PDA ...