Theoretische Informatik - Aufgaben

Nichtdeterministischer endlicher Automat

 aufwärts

Aufgabe:  

  1. Gegeben ist das Alphabet A = {a, b} und der reguläre Ausdruck

    R   =   b(a|b)*  |  (a|b)*bb

    der die Sprache aller Wörter erzeugt, die mit b anfangen oder mit bb enden.

    Konstruieren Sie nach dem unter

    http://www.inf.fh-flensburg.de/lang/theor/regulaerer-ausdruck-zu-automat.htm

    angegebenen Verfahren auf systematische Art und Weise aus dem regulären Ausdruck R einen nicht­deterministischen endlichen Automaten. Geben Sie die einzelnen Schritte des Konstruktionsverfahrens an.

     

  2. Gegeben ist der folgende (deterministische) endliche Automat, der alle Wörter über dem Alphabet A = {a, b} erkennt, die eine gerade Anzahl von b's enthalten.

    Automat

    Erzeugen Sie nach dem unter

    http://www.inf.fh-flensburg.de/lang/theor/automat-zu-regulaerer-ausdruck.htm

    angegebenen Verfahren aus dem Automaten einen regulären Ausdruck.

     

 

 

 

up

 

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