We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

924 questions
Filter by
Sorted by
Tagged with
165 views

### Computing follow sets conservatively for a PEG grammar

Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
163 views

376 views

### Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
987 views

### Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
126 views

### Is the set of LL(*) grammars the same as the set of CFG grammars?

Is the set of LL(*) grammars the same as the set of context-free grammars?
2k views

### Proof that a language involving $gcd$ is not context-free

How would you prove that the following language is not context-free? $$L= \{a^n b^m |\, gcd(n,m)=1 \}$$ I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.
935 views

### reduce reduce and shift reduce error in LALR grammar

I have to write a grammar for Pascal, and there is just one thing that is causing problems. Lets say we have operators (sorted by priority from low to high): Postfix ...
1k views

### Are there other ways to describe formal languages other than grammars?

I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
1k views

### Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
4k views

### How can I prove this language is not context-free?

I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
585 views

### Can every linear grammar be converted to Greibach form?

Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$? ($T$ is the set of ...
384 views

11k views

### Language theoretic comparison of LL and LR grammars

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...