Relation between simple and regular grammars

Problem Detail: 

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) grammars which are very similar to each other.

What relation exists between these? What is the difference? Can you create (non-deterministic) finite automata for simple grammars (obviously without using a stack)?

Asked By : Soroush

Answered By : David Lewis

A Simple Grammar (s-grammar) is one in which every production is of the form $A \rightarrow aB_1B_2...B_n$ where $a$ is a terminal and all $B_i, i\geq0 $ are non-terminals, and there is only one production with any pair $\langle A,a\rangle$.

Clearly, every s-language (produced by an s-grammar) is unambiguous and easily parsed, since each terminal symbol from left-to-right and non-terminal uniquely determine the production to apply. For example, if the string is $abc$, then the pair $\langle S,a\rangle$ uniquely determines the first production of the parsing, and so on for each terminal and the non-terminal to its immediate right. Thus, a language defined by an s-grammar can be parsed one symbol at a time, without lookahead, yielding linear parsing time, in fact, time $|x|$.

S-grammars are not terribly important in their own right, since most real languages exceed their power. But they are a stepping stone to other grammars parsed in linear time, such as $LL(k)$ grammars in which there is a bound $k$ on the lookahead needed to determine a production during parsing. In effect, an s-grammar is an $LL(0)$ grammar.

The connection to automata is that an s-langauge can be parsed with a pushdown automaton with a single state which just looks at the input symbol and top stack symbol to determine a string of stack symbols to push. But since the s-grammar...

$S \rightarrow aSB|\#\\ B\rightarrow a$

...generates non-regular $\{a^i\#a^i:i \geq 0\}$, s-languages cannot in general be recognized by finite-state automata, deterministic or non-deterministic.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1958