# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

1,030 questions
Filter by
Sorted by
Tagged with
971 views

### Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
884 views

### What would be CFG for all strings which does not contain bbb?

Is there a way to get complement? Following is my solution for CFG of all strings that DON'T contain bbb. ...
54 views

### Some Algorithm on Decidablitly [closed]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
182 views

### Is this $LL(1)$ grammar valid?

Is the following a valid $LL(1)$ grammar: \begin{align} S &\rightarrow L \ \\ L &\rightarrow M L_2 \\ L_2 &\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M &\...
1k views

### Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
122 views

79 views

### Chomsky Normal Form of |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...
2k views

### Eliminating Null Productions from Context Free Grammar

Here is a problem I am trying to solve: S -> 0A0 | 1B1 | BB A -> C B -> S | A C -> S | e I know that C is nullable (since it produces an epsilon) and ...
95 views

### What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|Īµ