# Tag Info

### Is the emptiness problem for PEGs decidable?

I should have done my research better before asking. The original paper introducing PEGs (Parsing Expression Grammars: A Recognition-Based Syntactic Foundation by Bryan Ford) actually contains a proof ...

### Dragon book exercise 4.4.5, why is aaaaaa not recognized by the recursive descent parser?

When you look at the parser's process, you see the entire text to be parsed, and naturally make judgements based on that knowledge. But that's not the way the parser works. So your strategy makes it ...
Accepted

### How to identify Context-Sensitive Grammar?

You are right: the grammar in your example is strictly speaking not context-sensitive. It is a monotonic (or non-contracting) grammar. In those grammars the main restriction is that the lefthand side ...
Accepted

Accepted

### Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n

No. Every context-free grammar generates a context-free language. If you can find a context-free grammar for a language, then the language is context-free. That assumes the claimed grammar is ...
Accepted

### Is THEADS the same as FIRST?

I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. ...

### Decidability of a context free Grammar

"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with ...
Accepted

### Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

$S \rightarrow aSb/A$ $A \rightarrow \epsilon/a/aa/aaa/B$ $B \rightarrow bB/\epsilon$
Accepted

### Prove a stronger version of the pumping lemma for context-free languages

Proof Idea for the usual pumping lemma Let $z$ be a very long string in $L$. A parse tree for $z$ is so tall that it must contain some long path from the start symbol at the root of the tree to one of ...

$w$ and $x$ are binary strings. Clearly $|wx|=|xw|$ and $|wx|_0=|xw|_0$. Suppose $wx$ and $xw$ differ only at position $i$, so that $(wx)[i]\ne(xw)[i]$, $(wx)[1..i-1]=(xw)[1..i-1]$, and $(wx)[i+1..n+k]... 2 votes ### Is$\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$context-free for some infinite regular language$A$? Let$F=\{x2y : |x| = |y|,\ x\in \{0\}^*,\ y\in\{0,1\}^*,\ d(x,y) = 1\}$, the language of all strings$0^n2y$where$y$consists of$n-10$s and one$1$. Note that$F=\{0^p00^q20^q10^p: p\ge0, q\ge0\}...
May I propose the following indexed grammar $G= ( \{S,A,C\}, \{a,b,c,d\}, \{f\}, S )$: $S[\sigma] \to S[f\sigma]$ $S[\sigma] \to A[\sigma]\, C[\sigma]$ $A[f\sigma] \to a\, A[\sigma]\, b$, \$\quad A[\...