# Tag Info

## Hot answers tagged formal-grammars

### 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 ...
• 12.3k

### 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 ...
• 11.2k
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 ...
• 27.6k
Accepted

• 23.4k
Accepted

• 270k

### 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 ...
• 141k
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. ...
• 137

### 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 ...
• 11.2k
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$
• 468
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 ...
• 34k

• 34k
Accepted

### Formal language rewrite rules: strange notation

Yes, I think that's basically the intent. I guess the book is trying to write grammars without grammatical symbols. For me, it's abuse of notation, but that's pretty common. Because there is no formal ...
• 11.2k
1 vote

### What's grammar for a^n b^n c^n d^n

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[\...
• 27.6k

Only top scored, non community-wiki answers of a minimum length are eligible