7
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ I am not familiar with simple grammars, can you recall the definition or give a reference? $\endgroup$ – jmad May 20 '12 at 21:28
13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Another way to compare them is by their decision problems. For simple grammars, the equivalence problem (whether two grammars generate the same language) is decidable, while the inclusion problem (whether one grammar generates a subset of the language generated by the other grammar) is not. For regular grammars, both problems are decidable. $\endgroup$ – reinierpost Aug 23 '16 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.