Greibach normal form

The Greibach normal form is a theoretical computer science term that is of interest in connection with context-free languages . It is named after the US computer scientist Sheila A. Greibach and describes a normal form of context-free grammars . Every context-free grammar, from which the empty word cannot be derived, can be transformed into a Greibach normal form. The outstanding property of the Greibach normal form is that exactly one terminal character is created for each derivation step . This makes it the natural intermediate step in transforming a context-free grammar into an equivalent nondeterministic push-down automaton without transitions. ${\displaystyle \varepsilon }$

Another normal form for context-free grammars is the Chomsky normal form .

Formal definition

Let be a context-free grammar (see Chomsky hierarchy ), i.e. , with . It should be the amount of non-terminal symbols , the set of terminal symbols , the set of production rules and the start symbol . Be the empty element . ${\displaystyle G}$ ${\displaystyle G\in {\mbox{Typ}}_{2}}$ ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle \varepsilon \notin L\left(G\right)}$

${\displaystyle G}$is in Greibach normal form ( GNF for short ), if all productions from have the form with , where is a terminal symbol and and are for non-terminals. The special thing about this form is that there is exactly one terminal symbol on the right-hand side of each production, followed by any number of non-terminals. In particular, it is possible that there is only one terminal symbol on the right side of the production. ${\displaystyle P}$ ${\displaystyle A\rightarrow bB_{1}\ldots B_{k}}$ ${\displaystyle k\geq 0}$ ${\displaystyle b}$ ${\displaystyle A}$ ${\displaystyle B_{i}}$ ${\displaystyle i\in \{1,\ldots ,k\}}$

With you get a regular grammar as a special case of a context-free grammar in Greibach normal form. ${\displaystyle k\in \{0,1\}}$

For everyone with there is a , with , in Greibach normal form. ${\displaystyle G'\in {\mbox{Typ}}_{2}}$ ${\displaystyle \varepsilon \notin L\left(G'\right)}$ ${\displaystyle G\in {\mbox{Typ}}_{2}}$ ${\displaystyle L\left(G\right)=L\left(G'\right)}$

However , it must never appear on the right side of a production. This ensures that languages ​​that contain the empty word can also be generated from a grammar in Greibach normal form. ${\displaystyle \left(S,\varepsilon \right)\in P}$ ${\displaystyle S}$

Construction of the GNF

The following algorithm converts a grammar from the Chomsky normal form to the Greibach normal form. The algorithm is of theoretical importance because it shows that any context-free grammar, from which the empty word cannot be derived, can be transformed into a Greibach normal form. The generated Greibach normal form is not minimal and there are algorithms with better running times that calculate small Greibach normal forms. ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$

notation

The following are:

• ${\displaystyle A_{i},B_{i}\in N,i\in \mathbb {N} }$Non-terminals (here represents existing non-terminal symbols and those newly introduced in the scheme) ${\displaystyle A_{i}}$ ${\displaystyle B_{i}}$
• ${\displaystyle a\in \Sigma }$ Terminals and
• ${\displaystyle V=\Sigma \cup N}$ the vocabulary of grammar
• ${\displaystyle x,y\in N^{*}}$Consequences of non-terminals (e.g. ) ${\displaystyle x=A_{1}A_{2}A_{3}}$
• ${\displaystyle \alpha ,\beta \in V^{*}}$Sequences of terminals and non-terminals (e.g. ) ${\displaystyle x=aA_{1}A_{2}}$

preparation

First, you bring the grammar into Chomsky normal form. An arbitrary total order on the nonterminal is required for the scheme given below . To do this, you can rename the occurring nonterminal in with . To do this, proceed as follows: ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle n=|N|}$

• The first nonterminal that occurs is renamed to. ${\displaystyle A_{1}}$
• The second occurring nonterminal is renamed to. ${\displaystyle A_{2}}$
• This scheme continues until all nonterminals that occur have been replaced.

Example: ${\displaystyle P=\{S\rightarrow ADE{,}A\rightarrow aDG{,}G\rightarrow b\}}$

• The first variable that occurs is , and is therefore renamed to. ${\displaystyle S}$ ${\displaystyle A_{1}}$
• The second variable that occurs is , and is therefore renamed to. ${\displaystyle A}$ ${\displaystyle A_{2}}$
• if you continue this scheme, you come to ${\displaystyle P=\{A_{1}\rightarrow A_{2}A_{3}A_{4}{,}A_{2}\rightarrow aA_{3}A_{5}{,}A_{5}\rightarrow b\}}$

Phase 1

At this stage, the algorithm uses the following two forms of rule substitution. After this step , that applies to all the rules of grammar . ${\displaystyle A_{i}\rightarrow A_{j}\,x}$ ${\displaystyle i<j}$

Start of productions

With this replacement rule, the algorithm removes all rules of the . The prerequisite is that there are no recursive rules for the non-terminal . The rules of form are then replaced by replacing the nonterminal with its productions. ${\displaystyle A_{i}\rightarrow A_{j}x}$ ${\displaystyle A_{j}}$ ${\displaystyle A_{i}\rightarrow A_{j}x}$ ${\displaystyle A_{j}}$

Regel1( ${\displaystyle A_{i},A_{j}}$)
 für alle  ${\displaystyle A_{i}\rightarrow A_{j}\,x}$
    für alle  ${\displaystyle A_{j}\rightarrow \beta }$
       Füge  ${\displaystyle A_{i}\rightarrow \beta \,x}$ hinzu
    ende
    Entferne  ${\displaystyle A_{i}\rightarrow A_{j}\,x}$
 ende

Example: with becomes to . ${\displaystyle A_{2}\rightarrow A_{1}x}$ ${\displaystyle A_{1}\rightarrow A_{3}{|}A_{4}}$ ${\displaystyle A_{2}\rightarrow A_{3}x{|}A_{4}x}$

Replace left recursive rules

Left recursive rules are of the form ; H. a variable can again derive on itself. Repeated insertion makes it easy to see that, through left-recursive rules, exactly the regular expression ${\displaystyle A_{i}\rightarrow A_{i}\,x_{1}|A_{i}\,x_{2}|\ldots |A_{i}\,x_{n}|\beta _{1}|\beta _{2}|\ldots |\beta _{n}}$

${\displaystyle (\beta _{1}|\beta _{2}|\ldots |\beta _{n})(x_{1}|x_{2}|\ldots |x_{n})^{*}}$

can be generated. This can easily be achieved differently:

The rules for left-recursive are replaced by: ${\displaystyle A_{i}}$

${\displaystyle A_{i}\rightarrow \beta _{1}|\beta _{2}|\ldots |\beta _{n}|\beta _{1}\,B_{i}|\beta _{2}\,B_{i}|\ldots |\beta _{n}\,B_{i}}$

and adds new rules for : ${\displaystyle B_{i}}$

${\displaystyle B_{i}\rightarrow x_{1}|x_{2}|\ldots |x_{n}|x_{1}\,B_{i}|x_{2}\,B_{i}|\ldots |x_{n}\,B_{i}}$

Regel2( ${\displaystyle A_{i}}$)
 für alle  ${\displaystyle A_{i}\rightarrow \beta }$
    Füge  ${\displaystyle A_{i}\rightarrow \beta \,B_{i}}$ hinzu
 ende
 für alle  ${\displaystyle A_{i}\rightarrow A_{i}\,x}$
    Füge  ${\displaystyle B_{i}\rightarrow x}$ hinzu
    Füge  ${\displaystyle B_{i}\rightarrow x\,B_{i}}$ hinzu
    Entferne  ${\displaystyle A_{i}\rightarrow A_{i}\,x}$
 ende

algorithm

The algorithm applies the above two replacement rules for to , so that rules of the From are always replaced first and then left-recursive rules are also eliminated. ${\displaystyle A_{1}}$ ${\displaystyle A_{m}}$ ${\displaystyle A_{i}\rightarrow A_{j}\,x,~i>j}$ ${\displaystyle A_{i}}$

 für i:=1 bis m
    für j:=1 bis i-1
       Regel1( ${\displaystyle A_{i},A_{j}}$)
    ende
    Regel2( ${\displaystyle A_{i}}$)
 ende

From now on there are only rules of form or form . In particular, all rules start with a terminal symbol on the right. ${\displaystyle A_{i}\rightarrow A_{j}\,x,~i<j}$ ${\displaystyle A_{i}\rightarrow x}$ ${\displaystyle A_{m}}$

Phase 2

In this phase all rules are transformed into the form via the non-terminals . The algorithm starts with the rules and replaces rules that will start with a nonterminal by employing the nonterminal's productions. This makes use of the fact that when rules are considered, the rules for are already in the desired form. ${\displaystyle A_{i}}$ ${\displaystyle A_{i}\rightarrow a\,N^{*}}$ ${\displaystyle A_{m-1}}$ ${\displaystyle A_{i}}$ ${\displaystyle A_{j}}$ ${\displaystyle j>i}$

 für i:=m-1 bis 1
    für j:=i+1 bis m
         Regel1( ${\displaystyle A_{i},A_{j}}$)
    ende
 ende

Phase 3

In the last step, all rules are transformed into the Greibach normal form via the new non-terminals . Rules that begin with a nonterminal are replaced by using the productions of that nonterminal. ${\displaystyle B_{i}}$

 für alle  ${\displaystyle B_{i}\rightarrow A_{j}\,x}$
    für alle  ${\displaystyle A_{j}\rightarrow \beta }$
       Füge  ${\displaystyle B_{i}\rightarrow \beta \,x}$ hinzu
    ende
    Entferne  ${\displaystyle B_{i}\rightarrow A_{j}\,x}$
 ende

This makes use of the fact that the rules are all already in Greibach normal form and that they never appear as the first symbol on the right-hand side of a rule. ${\displaystyle A_{j}}$ ${\displaystyle B_{i}}$

A stricter variant of the Greibach normal form

It is also possible to transform the productions of a context-free grammar into Greibach normal form so that a maximum of 2 variables appear on each right-hand side. The resulting productions then have the form , or . ${\displaystyle A_{i}\rightarrow a}$ ${\displaystyle A_{i}\rightarrow aV}$ ${\displaystyle A_{i}\rightarrow aV_{1}V_{2}}$

Construction of a basement automat from the GNF

To construct a push-down automaton from a grammar in GNF , choose the state set of as , the basement alphabet , the band alphabet , the basement start symbol and the set of end states . Choose as transition relation . accepted over empty basement. Proof by induction. ${\displaystyle G=(N,T,P,S)}$ ${\displaystyle M=(Z,\Sigma ,\Gamma ,\delta ,q_{0},Z_{0},F)}$ ${\displaystyle M}$ ${\displaystyle Z=\{q_{0}\}}$ ${\displaystyle \Gamma =N}$ ${\displaystyle \Sigma =T}$ ${\displaystyle Z_{0}=S}$ ${\displaystyle F=\emptyset }$ ${\displaystyle \delta (q_{0},a,A)=\{(q_{0},x):(A\rightarrow ax)\in P\}}$ ${\displaystyle M}$

literature

• Uwe Schöning : Theoretical Computer Science - in a nutshell . 5th edition. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.3 Context-Free Languages.
• Ingo Wegener : Theoretical Computer Science . An algorithm-oriented introduction. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 7.1 The Greibach normal form for context-free grammars.

Individual evidence

1. ^ Norbert Blum, Robert Koch: Greibach Normal Form Transformation Revisited . In: Information and Computation . 150, No. 1, 1999, pp. 112-118. doi : 10.1006 / inco.1998.2772 .
2. ^ Proof of the construction of the push-down automaton from the GNF