Theoretische Informatik

Greibach-Normalform

 aufwärts

Neben der Chomsky-Normalform gibt es für kontextfreie Grammatiken noch die Greibach-Normalform (nach S. Greibachzur Person).

Greibach-Normalform einer kontextfreien Grammatik

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik. G ist in Greibach-Normalform, wenn jede ihrer Produktionen die Form

Xgeht über nachau

mit X Element V, a Element T und u Element V* hat.

Zusätzlich ist die Produktion Sgeht über nachε als Ausnahme erlaubt, wobei dann das Startsymbol S nicht rekursiv sein darf.

Die rechte Seite jeder Produktion beginnt also stets mit einem Terminal­zeichen, danach kommen dann 0, 1, oder mehrere Variablen.

Die Greibach-Normalform ist somit eine Ver­allgemeinerung einer rechts­linearen Grammatik. Die Produktionen einer rechts­linearen Grammatik haben ebenfalls die Form Xgeht über nachau mit X Element V, a Element T, jedoch mit u Element V?, d.h. bei einer rechts­linearen Produktion darf u höchstens aus einer Variablen bestehen.

Satz:  Zu jeder kontext­freien Grammatik gibt es eine äquivalente kontextfreie Grammatik in Greibach-Normalform.

Die Ein­schränkung der Form der rechten Seiten der Produktionen einer Grammatik in Greibach-Normalform beschränken also nicht die Ausdrucks­stärke der Grammatik.

 

Weiter:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 04.01.2010   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik