Theoretische Informatik - Aufgaben

Spiegelbild einer regulären Sprache

 aufwärts

Aufgabe:  Der folgende nicht­deterministische endliche Automat erkennt die Sprache

L  =  a(a|b)*b | b

also alle Wörter, die mit a anfangen, dann mit a's und b's weitergehen und schließlich mit b enden, sowie das Wort, das nur aus einem b besteht.

Automat

Wie kann man diesen Automaten so umkonstruieren, dass er das Spiegelbild von L erkennt, also die Sprache LR, die aus allen gespiegelten, d.h. rückwärts gelesenen Wörtern von L besteht?

 

Beweisen Sie allgemein: Das Spiegelbild einer regulären Sprache ist regulär.

 

 

 

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