# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,144 questions
Filter by
Sorted by
Tagged with
37 views

31 views

### I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
29 views

### CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
52 views

### Regular grammar for language that does not contain "abab"

I tried this : $V = \{S,A,B\}$ and $T = \{a,b\}$. $S \rightarrow aS | \epsilon | abaAS | BS$ $A \rightarrow a | aA$ $B \rightarrow bB | \epsilon$ Any thoughts/objections?
13 views

### Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
19 views

### What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
23 views

### LALR lookahead is wrong, why?

I am studying LALR(1) parser and I have this question: Consider the following Grammar S - > V = E E - > F | E+F F - > V | int | (E) V - > id Construct the LALR(1) parsing table for this ...
### Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]
Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma. So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...