Theoretische Informatik - Aufgaben

Nichtdeterministischer endlicher Automat

 aufwärts

Aufgabe:  

Geben Sie für jede der folgenden Sprachen über dem Alphabet A = {a, b} einen möglichst einfachen nicht­deterministischen endlichen Automaten an, der sie erkennt.

Zeichnen Sie zunächst den betreffenden nicht­deterministischen Automaten als Zustandsdiagramm.

Geben Sie dann die Übergangs­relation des Automaten in die jeweilige unten­stehende Tabelle ein und simulieren Sie den Automaten mit ein paar Eingabe­wörtern.

 

 

L1  =  Menge aller Wörter, die höchstens ein b enthalten:

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
     
     
     
     
     
     

       


 

L2  =  Menge aller Wörter, die das Teilwort bb enthalten:

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
     
     
     
     
     
     
     
     

       

 

L3  =  Menge aller Wörter, die das Teilwort bb nicht enthalten:

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
     
     
     
     
     
     

       


 

L4  =  Menge aller Wörter, die eine ungerade Länge haben:

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
     
     
     
     
     
     

       


 

 

 

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