4
votes
Accepted
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
Let $G = (\Sigma, V, P, S)$ a context-free grammar.
Let us start with some simple statements:
Lemma 1: $G$ is right-regular (rules $X\to \varepsilon$, $X\to a$ and $X\to aY$ only) if and only if it is ...
- 16.9k
2
votes
Does a language recognizer require an unambiguous context-free grammar?
It depends on the parsing technique used.
General context-free parsing techniques (such as GLR and Earley) can handle arbitrary grammars just fine.
In practice, we often see more limited parsers that ...
- 5,941
2
votes
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
Here's a solution using language equations.
With every grammar $G$ with terminals $\Sigma$, non-terminals $V = \{S_1, S_2, ..., S_n\}$ and start variable $S_1$ we can associate a system of equations ...
- 1,624
2
votes
Accepted
What is the language generated by the context free grammar $S \rightarrow aSb \ | \ bSa| \ \epsilon $
Since each production introduces one letter to the left and one letter to the right of $S$, we see that $S$ keeps sitting in the middle of the word. The two subwords left and right of $S$ are “doubly ...
- 2,222
1
vote
What is the language generated by the context free grammar $S \rightarrow aSb \ | \ bSa| \ \epsilon $
It can be tricky to go from formal specification to informal specification.
In a rigorous sense, the best description of the language is the grammar you have already provided.
But we can try to ...
- 387
1
vote
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
There is not much difference (technically) between a nonderterministic automaton and a linear grammar. A single step from state to state reading a letter is equivalent to a nonterminal generating a ...
- 31.1k
1
vote
How did the author derive a string from a specific grammar?
The step you describe does not appear in the derivation given in the book.
However, I still think it contains two mistakes:
There is a step $AABB \Rightarrow AAbb$ followed by $AAbb \Rightarrow AAABb$....
- 16.9k
Only top scored, non community-wiki answers of a minimum length are eligible