25. Regular¨ e Sprachen · 25 REGULA¨RE SPRACHEN 178 (wobei X Y N;a1 F an T) durch zulassige¨ aqui¨ valente Regeln ersetzt werden. Im alle von Regeln (R1) und (R2) geht man hier

25.RegulareSprachen

Wir beschließenunsereBetrachtungder Sprachklassender Chomsky-Hierarchiemit deneinseitiglinearenSprachen,dievon denrechts-bzw. linkslinearenGrammati-kenerzeugtwerden.Wir werdenzeigen,dassdie von diesenbeidenGrammatiktypenerzeugtenSprachendieselbensind, d.h. RLIN � LLIN gilt, und dassdieseSprach-klasseechtin derKlasseder linearenunddamitderkontextfreienSprachenenthaltenist.

Die einseitiglinearenSprachensindaufvielfaltigeWeisebeschriebenworden.Hierwerdenwir zwei Charakterisierungenvon RLIN betrachten:zum einendurch Be-schreibung der erforderlichenMaschinen,die zur Erkennungder Sprachenin RLINausreichen,zumanderendurchAbschlusseigenschaftenvon RLIN. Wir werdenhier-bei sehen,dassRLIN die Klasseder von (deterministischenoder nichtdeterministi-schen)endlichenAutomatenerkanntenSprachenist. Ein endlicherAutomatkannalsoff-line (1-Band)Turingmaschineinterpretiertwerden,diedieEingabevon links nachrechtsliest, ohnedasArbeitsbandzu benutzen,und dannsofort akzeptiertoderver-wirft. D.h. dasWortproblemfur einerechtslineareGrammatikist in Realzeitundoh-ne Speicherverbrauchlosbar. Die zweiteCharakterisierungzeigt,dassRLIN mit derKlassederregularenSprachenzusammenfallt (die dieserSprachklasseauchdenin derRegel gebrauchtenNamengibt). DieseKlasseerhalt mandurchAbschlussderendli-chenSprachengegeneinfacheSprachoperationen.

Wir beginnenunsereUntersuchungvon RLIN mit einerNormalformderrechtsli-nearenSprachen,ausderwir eineverscharfte Form desPumpingLemmasfur RLINableitenwerden,diedieTrennungvon RLIN undLIN erlaubt.

25.1 DEFINITION. Eine rechtslineareGrammatikG �� N � T � P� S� ist in Chomsky-Normalform, falls sieλ-treuist undnebendereventuellvorkommendenλ-RegelS � λnur RegelnderFormenX � aY undX � a (X � Y � N � a � T) enthalt.

25.2 SATZ. (NORMALFORMSATZ FUR RLIN) Zu jederrechtslinearenGrammatikGkannmaneffektiv eineaquivalenterechtslineareGrammatikG� in Chomsky-Normal-form angeben.

BEWEIS. Die Uberfuhrungder GrammatikG �� N � T � P� S� in die GrammatikG� �� N �� T � P�� S� erfolgt in den entsprechendenSchrittenwie bei der UmformungeinerkontextfreienGrammatikin die Normalform.Da G kontextfrei ist, konnenwir dir λ-Treuewie zuvor sicherstellen.(Diesfuhrt zu keinenunzulassigenRegeln.)EsmussenalsonochRegelnderForm

(R1) X � a1 �� anY � n � 2�(R2) X � a1 �� an

� n � 2�(R3) X � Y

25 REGULARE SPRACHEN 178

(wobeiX � Y � N;a1 � � � an � T) durchzulassigeaquivalenteRegelnersetztwerden.ImFalle von Regeln(R1) und(R2) gehtmanhier wie beimVerkurzenzu langerKonklu-sionenim kontextfreienFall vor. D.h. zu einerRegel (R1) fuhrt manneueVariablenX2 � �� Xn ein undersetztdieRegel danndurchdieRegeln

X � a1X2 � X2 � a2X3 � � � � � Xn� 1 � an� 1Xn � Xn � anY �Fur RegelnderForm (R2) verfahrtmanebenso,wobeimanlediglich dieabschließen-deSimulationsregelXn � anY durchXn � an ersetzt.Variablenumbenennungen(R3)eliminiert manschließlichgenauwie im kontextfreienFall. �

Fur linkslineareGrammatikenist dieChomsky-Normalformentsprechenddefiniert(stattX � aY hatmanhier X � Ya), undmanzeigtdenNormalformsatzauf dieselbeWeise.

Man beachte,dassbei der HerleitungeinesTerminalwortesw � a1 �� an in einerrechtslinearenGrammatikin Chomsky-Normalformdie Buchstabenvon w Schritt furSchrittvon links nachrechtserzeugtwerden,unddie nachm�� n� SchrittenerhalteneSatzformnachdem bereitsabgeleitetenTeilwort a1 � � � am mit einerVariablenXm� 1

endet,diedieHerleitungdesRestwortesam� 1 � � � an erlaubt.D.h.

S � X1 � a1X2 � a1a2X3 �� a1 �� an� 1Xn � a1 � � � an (25.1)

Der Herleitungsbaumist alsoim Wesentlichenzu demamweitestenrechtsliegendenPfaddegeneriert,derdieVariablenzurErzeugungderRestworterenthalt:

S � X1

a1 X2

a2

Xn� 1

an� 1 Xn

an

��

��

Fur einelinkslineareGrammatikin NormalformsehenHerleitungsbaumegeradespie-gelbildlich hierzu aus.Wir konnenhierausfolgern, dassdie linkslinearenSprachengeradedie SpiegelbilderrechtslinearerSprachensind,waswir spaterzum NachweisderGleichheitdieserSprachklassenverwendenwerden.

25.3 KOROLLAR. Fur eineSpracheL gilt L � RLIN genaudann,wennLR � LLINgilt. Hierbeiist LR �� wR : w � L � dieMengederSpiegelbilderderWorterin L.

BEWEIS. Wir zeigendie Implikation”L � RLIN � LR � LLIN“ . Die Ruckrichtung

zeigt mananalog.Sei alsoL � RLIN. NachSatz25.2konnenwir einerechtslineareGrammatikG �� N � T � P� S� in Chomsky-Normalformangeben,dieL erzeugt.Ersetzenwir in G die RegelnderForm X � aY durchdie RegelnX � Ya, soerhaltenwir eine


linkslineareGrammatikG� �� N � T � P� � S� . DurchInduktionnachderWortlangevon wzeigtmannun,dass

S !�G

wX " S !�G# XwR

fur w � T ! und X � N $ � λ � . Insbesonderegilt alsoL � G� � � L � G� R und damit LR �LLIN. �Die spezielleGestaltvon Herleitungenin rechtslinearenGrammatikenin Chomsky-Normalform erlaubt,dasPumpingLemma(s. Satz24.7) fur RLIN zu verscharfen.Hierzubeobachtetman,dassin dendortim BeweisgefundenenZerlegungenz � uvwxyhinreichendlangerWorterz die Teile x undy nunweggelassenwerdenkonnen.DieseTeile stehennamlich in der Herleitungrechtsvon einerVariablen,wahrendbei einerrechtslinearenHerleitungdieeinzigevorkommendeVariableimmerganzrechtssteht.

25.4 SATZ. (PUMPING LEMMA FUR RLIN) Zu jederrechtslinearenSpracheL � Σ !gibt eseineZahl p �&% , sodassjedesWort z � L mit ' z'(� p eineZerlegungz � uvw inTeilworteru � v� w � Σ ! besitzt,die folgendeEigenschaftenhat:

(i) v )� λ

(ii) ' vw'+* p

(iii) , n �&% � zn� uvnw � L � .

Weiterlasstsicheingeeignetesp effektiv ausjederrechtslinearenGrammatikG, dieLerzeugt,berechnen.

BEWEIS. Sei L gegeben,und nachSatz25.2 sei G �� N � T � P� S� eine rechtslineareGrammatikin Chomsky-Normalform,dieL erzeugt.Wir zeigen,dassp ��- N -/. 1 diegewunschtenEigenschaftenhat.Seialsoz ein beliebigesWort derSpracheL, fur des-senLange ' z' � n, n � p gilt. Um eineZerlegungz � uvwvon z mit dengewunschtenEigenschaftenanzugeben,betrachtenwir eineHerleitungvon z � a1 � � � an in G. Wieobenbeobachtet,hatdiesedieGestalt(25.1).Dan � p 0 - N - nachAnnahme,konnenwir k maximalund l (maximal)passendmit 1 * k � l * n undXk

� Xl wahlen.(D.h.Xk

� Xl ist die letzte”Variablenwiederholung“ in derHerleitung.)WegenderMaxima-

lit atvon k gilt dann

n 1 k * - N -2� p (25.2)

undausderAbleitung(25.1)ergibt sichfur X � Xk� Xl

S !� a1 �� ak � 1X (25.3)

X !� ak � � � al � 1X (25.4)

X !� al �� an � (25.5)

Setzenwir alsou � a1 � � � ak � 1, v � ak �� al � 1 undw � al � � � an, sogilt z � uvw, v )� λ(da l 0 k) und ' vw' � ' ak �� an ' � n 1 k . 1 * p (nach(25.2)),weshalbdie Zerlegungz � uvwdie Bedingungen(i) und(ii) erfullt. Zum Nachweisvon (iii) beobachtetman,dassmanzn

� uvnw in G ableitenkann,indemmanmit derSchrittfolge(25.3)beginnt,danach(25.4)n-fachiteriert,unddieHerleitungmit (25.5)beendet. �


25.5 KOROLLAR. RLIN 3 LIN. Da LIN in KF enthaltenist, gilt alsoinsbesondereauchRLIN 3 KF.

BEWEIS. Zu derSpracheL �4� 0m1m : m � 1 � habenwir in Beispiel21.9einelineareGrammatikangegeben.EsgenugtalsoL )� RLIN zuzeigen.Wir beweisendiesindirektundgehenvon derWiderspruchsannahmeL � RLIN aus.NachSatz25.4gibt esdanneineZahl p, sodasseszu jedemWort z � L mit ' z'50 p eineZerlegungz � uvw mitdendortangegebenenEigenschaften(i)-(iii) gibt. Wahlenwir z � 0p1p, sogilt fur dieZerlegungz � uvw, dassv )� λ (nach(i)) und ' vw'+* p (nach(ii)), weshalbnachWahlvon z, vw vollstandig in dem zweitenWortteil 1p von z enthaltenist. Fur dasWortz0

� uv0w � uw gilt also #0� z0 �60 #1

� z0 � und daherz0 )� L. Dies widersprichtaberEigenschaft(iii) derZerlegung. �Wir wendenuns nun den aquivalentenCharakterisierungender rechtslinearenSpra-chenzu.Wir fuhrendie hierzubenotigtenKonzeptezunachstein undzeigendanndieAquivalenzder Konzeptein einemRingschluss.Wir beginnenmit der Charakterisie-rung von RLIN uberAbschlusseigenschaften,die auf dassyntaktischeKonzeptderregularenAusdruckezuruckgreift.

25.6 DEFINITION. Die regularenAusdrucke ubereinemAlphabetΣ sindinduktiv de-finiert durch:

i) /0 ist ein regularerAusdruck.

ii) JederBuchstabea � Σ ist ein regularerAusdruck.

iii) Sindα � β regulareAusdrucke,soist auch � αβ � ein regularerAusdruck.

iv) Sindα � β regulareAusdrucke,soist auch � α $ β � ein regularerAusdruck.

v) Ist α ein regularerAusdruck,soist auchα ! ein regularerAusdruck.

RegulareAusdruckeuberΣ sind alsonachdenobenangegebenenRegeln gebil-deteWorter uberdemAlphabetΣ � � Σ $ � /0 � � ��(�7$6� ! � . JederAusdruckα reprasentierthierbeieineSpracheL � α �98 Σ ! , diewir alsnachstesdefinieren.

25.7 DEFINITION. Die voneinemregularen Ausdruck α uberΣ dargestellteSpracheL � α �98 Σ ! ist durchInduktionnachdemAufbauvon α definiertdurch

i) L � /0 � � /0

ii) L � a� �� a � � a � Σ �iii) L �:� αβ �;� � L � α � L � β � , wobei LL � �<� ww� : w � L & w�/� L �� die Verkettungder

SprachenL undL � ist.

iv) L �:� α $ β �;� � L � α �=$ L � β �v) L � α ! � � L � α � ! , wobeiL ! �>� w1 � � � wn : n � 1& w1 � � � � � wn � L �?$ � λ � dieIteration

von L ist.

EineSpracheL 8 Σ ! heisstregular, wennsiedurcheinenregularenAusdruckuberΣdargestelltwerdenkann.REG (REGΣ) ist dieKlassederregularenSprachen(uberΣ).


25.8 BEISPIEL . Die SpacheL �@� 0m1n : m� n � 0 � wird durch den Ausdruckα �� 0! 1! � dargestellt,namlichL �4� 0 � ! � 1 � ! . Entsprechendstellt �;� 00! � � 11! �;� die Spra-cheL �4� 0 � � 0 � ! � 1 � � 1 � ! �4� 0m1n : m� n � 1 � dar. A25.9 BEISPIEL . Die SpracheL �4� w � Σ !2 : ' w ' gerade� wird durchdenAusdurck

�:�;�;� 00�B$ � 01�:�B$ � 10�:�B$ � 11�:� !dargestellt.Der Ausdruckin der außerenKlammer stellt namlich die SpracheL � �� 00� 01� 10� 11 � �� w � Σ !2 : ' w ' � 2 � dar, undL ist die Iterationvon L � . (Manbeachte,dassjedeIterationsspracheL ! dasleereWort enthalt. Insbesonderegilt /0 ! �� λ � .) AWenigertechnischlassensichdie regularenSprachenwie folgt beschreiben.

25.10 SATZ. Die KlasseREG der regularenSprachenist die kleinsteSprachklasse,die die endlichenSprachenenthalt und gegenVerkettung,Vereinigungund Iterationabgeschlossenist.

BEWEIS. DaREG alsAbschlussspeziellerendlicherSprachengegendieaufgefuhrtenOperationendefiniertist, genugt eszuzeigen,dassjedeendlicheSpracheregular ist:

25.11 LEMMA . JedeendlicheSpracheL 8 Σ ! wird durcheinenregularenAusdruckα uberΣ ! dargestellt.

BEWEIS. Der Beweis wird durch Induktion nachder Kardinalitat n �C- L - von Lgefuhrt. Ist n � 0, soist L leer, d.h.L � /0 � L � /0 � . Ist n � 1, soist L �� w � fur einWortw � Σ ! . Hier zeigenwir dieBehauptungdurchNebeninduktionnach ' w ' � m. Ist m � 0,soist w � λ, d.h.L �>� λ � � L � /0 ! � . Ist m 0 0, solasstsichw darstellenalsw � aw� mita � Σ und ' w� ' � m 1 1.Esist dannL � L �;� aβ �:� , wobeiβ einnachNebeninduktionsvor-aussetzungexistierenderregularerAusdruckzur Darstellungvon � w�� ist. Ist schließ-lich n 0 1, d.h.L �4� w1 � � � � � wn � mit n 0 1, soist L � L1 $ L2

�4� w1 �D$ � w2 � � �� wn � ,alsoL � L �:� β1 $ β2 �:� fur nachInduktionsvoraussetzungexistierendenDarstellungenβ1 undβ2 von L1 undL2. �

Fur spaterenGebrauchbeobachtenwir noch,dassREG gegenSpiegelbilderabge-schlossenist.

25.12 LEMMA . Fur regularesL 8 Σ ! ist dasSpiegelbild LR ebenfallsregular.

BEWEIS. Man zeigt die Behauptungdurch Induktion nachdemAufbau einesAus-drucksα, derL darstellt.Ist α � /0 oderα � Σ, soist L � L � α � � L � α � R � LR. Ist α vonderGestalt � βγ � , � β $ γ � oderβ ! , sofolgt dieBehauptungausderInduktionsvorausset-zungunterBerucksichtigungderIdentitaten

L �:� βγ �:� R � L � γ � RL � β � R

L �;� β $ γ �;� R � L � β � R $ L � γ � R

L � β ! � R � � L � β � R � !�

Als nachstesfuhrenwir dieendlichenAutomatenein.


25.13 DEFINITION. Ein deterministischer endlicher AutomatM ist ein 5-TupelM �� Σ � Z � δ � z0 � E � , wobei

E Σ einAlphabet(Eingabealphabet)

E Z eineendlicheMenge(MengederZustande)

E δ : Z F Σ � Z die Ubergangsfunktion

E z0 � Z derStartzustandund

E E 8 Z die MengederEndzustande

sind.Ist δ 8 � Z F Σ �GF Z eineRelation(Ubergangsrelation), soheißtM einnichtdeter-ministischerendlicherAutomat.

Der deterministischeAutomatM arbeitetwie folgt. Bei EingabeeinesWortesw �Σ ! liest M dasWort w Buchstabefur Buchstabeein und aktualisiertdabei laufendseinenZustand,wobei sich der jeweils nachsteZustandz� ausdemvorhergehendenZustandzunddemgelesenenBuchstabena gemaßδ ergibt (δ � z� a� � z� ). DieRechnungbeginntmit demStartzustandz0. Ist derAutomatnachvollstandigemEinlesenvonw ineinemZustandz � E, soakzeptierter dieEingabe.Sonstwird dieEingabeverworfen.

Im Falle einesnichtdeterministischenAutomatengilt fur denNachfolgezustandz�von z beimLesenvon a, dass�;� z� a�(� z� �H� δ gilt. Hier ist z� i. Allg. nicht eindeutigbe-stimmt(undbrauchti. Allg. garnicht zu existieren).Hier wird die Eingabeakzeptiert,falls eseinezulassigeRechnunggibt, die dasvollstandigeEinlesenermoglicht und ineinemEndzustandendet.

Formal beschriebenwir die ArbeitsweiseendlicherAutomatendurchZuordnungeinesUmformungssystems.Hierbeiidentifizierenwir fur einendeterministischenAu-tomatendie Ubergangsfunktionδ : Z F Σ � Z mit ihremGraphen,d.h. �:� z� a�I� z�J�2� δgenaudann,wennδ � z� a� � z� . Dieserlaubtuns,deterministischeendlicheAutomatenalsspeziellenichtdeterministischeAutomatenaufzufassen.

25.14 DEFINITION. Daszudemdeterministischenodernichtdeterministischenendli-chenAutomatenM �� Σ � Z � δ � z0 � E � gehorigeUmformungssystem

UM�4� KONM � � M �

bestehtausderKonfigurationenmenge

KONM� Z F Σ !

undderEin-Schritt-Relation�M

8 KONM F KONM mit

� z� aw� �M

� z� � w� genaudann,wenn �:� z� a�I� z� �K� δ �wobeiz� z� � Z, a � Σ undw � Σ ! . DieKonfiguration� z0 � w� heißtdieStartkonfigurationvonUM (M) beiEingabew. Die von M erkannteSpracheL � M �K8 Σ ! ist

L � M � �4� w � Σ ! : L z � E �:� z0 � w� !�M

� z� λ �;� � �


Die in Abschnitt3 eingefuhrtenBegriffe fur UmformungssystemeubertragenwirvonUM aufM. Mit DEA (NEA) bezeichnenwir dieKlassedervon(nicht)determinis-tischenendlichenAutomatenerkanntenSprachen.

Haufig stellt mankleinereendlicheAutomatendurchgerichteteGraphendar, de-ren Knoten mit den Zustanden,und derenKantenmit Buchstaben(folgen)markiertsind. Hierbei tragt die Kantevon Zustandz zu Zustandz� diejenigenBuchstabenaalsMarkierung,bei derenEinlesenderAutomatvon Zustandz in Zustandz� ubergeht(δ � z� a� � z�M� . DenStartzustandkennzeichnetmandurcheine(

”ausdemNichts“ ) ein-

gehende,unmarkierteKante.EndzustandewerdendurchDoppelkreisehervorgehoben.

25.15 BEISPIEL . Der deterministischeendlicheAutomatM �� Σ � Z � δ � z0 � E � mit Σ �� 0 � 1 � , Z �� zλ � z0N � z0N 1N � zFehler� , z0� zλ, E �4� z0N 1N � undderUbergangsfunktionδ

Z F Σ � Zzλ 0 z0Nzλ 1 zFehler

z0N 0 z0Nz0N 1 z0N 1Nz0N 1N 0 zFehler

z0N 1N 1 z0N 1NzFehler 0 zFehler

zFehler 1 zFehler

erkenntdieSpracheL � M � �� 0m1n : m� n � 1 � . Graphischwird dieserAutomatdarge-stellt durch

zλO z0N z0N 1NP QR S

zFehler

O0 T

0

O1 T

1

U U U U U U�V1

WWWWWWX 0

Y

0,1

A25.16 BEISPIEL . EinenendlichenAutomaten,derdie durchdrei teilbarenZahleninDezimaldarstellungerkennt,kannmanmit Hilfe derQuersummenregel (

”3 teilt genau

dannn, wenn3 die Quersumme(der Dezimaldarstellung)von n teilt“ ) konstruieren.Hierzumerktmansichim Zustandzi mod3, dassdieQuersummederbishereingelesenen


Zif fern denWert i modulo3 hat (i � 0 � 1 � 2). Die Zahl 0 behandeltmangetrenntundschließtgleichzeitigmit fuhrendenNullen beginnendeZif fernfolgenals unzulassigeDarstellungenaus.

zStartO

z0P QR S

zFehler

z0mod3P QR S

z1mod3

z2mod3

Z 0

Z 0 � � �� 9

[3,6,9

O1,4,7

\2,5,8

Y

0, � � � ,9

T

0,3,6,9

T

0,3,6,9

Y

0,3,6,9

]]]]]]]]] ^ 1,4,7] ] ] ] ] ] ] ] ]`_2,5,8

Z2,5,8

a

1,4,7b b b b b b b b b`c1,4,7

bbbbbbbbb d2,5,8

AWir zeigennundie AquivalenzderobeneingefuhrtenKonzepte.

25.17 SATZ. RLIN � LLIN � REG � DEA � NEA. DieseGleichungengeltenef-fektiv in demSinne,dassmanausderDarstellungeinerSprachein einemderKonzepteeffektiv DarstellungenderSprachein denanderenKonzeptenerhalt.

Zum BeweisdesSatzesfuhrenwir denRingschluss

REG 8 RLIN 8 NEA 8 DEA 8 REG (25.6)

durch,ausdem

RLIN � REG � DEA � NEA

folgt. Die fehlendeGleichheitRLIN � LLIN ergibt sichdannmit Hilfe derobenge-machtenBeobachtungenuberSpiegelbilder:

L � RLIN " L � REG �:� 25� 6�:�" LR � REG � Lemma25� 12�" LR � RLIN �:� 25� 6�:�" L �� LR � R � LLIN � Korollar25� 3�Die Behauptung(25.6)ergibt sichausdennachfolgendenLemmata.


25.18 LEMMA . Zu jedemregularenAusdruckα kannmaneffektiv einerechtslineareGrammatikangeben,diedievon α dargestellteSpracheerzeugt.

BEWEIS. Sei α ein regularerAusdruckuberΣ. Eine rechtslineareGrammatikGα�� Nα � Σ � Pα � Sα � mit L � α � � L � Gα � definiertmandurchInduktionnachdemAufbauvon

α.

α � /0: WahlePα� /0.

α � a � Σ: Pα enthalt nur dieRegel Sα � a.

α �<� βγ � : SeienGβ und Gγ nachInduktionsvoraussetzungexistierenderechtslineareGrammatikenmit L � Gβ � � L � β � und L � Gγ � � L � γ � , die o.B.d.A. in Chomsky-Normalformsind,und derenVariablenmengendisjunkt sind.Weitergehenwirzunachstdavon aus,dassGβ λ-frei ist. DannerzeugtGα

�e� Nβ $ Nγ � Σ � Pα � Sβ �dieSpracheL � α � � L � β � L � γ � , wobei

Pα�� X � aY : X � aY � Pβ ��$ � X � aSγ : X � a � Pβ ��$ Pγ �

Enthalt Gβ die λ-Regel Sβ � λ, so fugenwir zu Pα noch die Regel Sβ � Sγhinzu.

α �<� β $ γ � : Aus Gβ undGγ wie im vorhergehendenFall erhalt maneineGrammatikGα

�@� Nβ $ Nγ $ � Sα �B� Σ � Pα � Sα � zur Erzeugungvon L � α � � L � β �f$ L � γ � durchWahlderRegelmenge

Pα�� Sα � Sβ � Sα � Sγ �D$ Pβ $ Pγ �

α � β ! : Aus einernachInduktionsvoraussetzungexistierendenrechtslinearenGram-matik Gβ

�� Nβ � Σ � Pβ � Sβ � in Chomsky-Normalform zur Erzeugungvon L � β �erhalt maneinerechtslineareGrammatikGα

�� Nβ $ � Sα �B� Σ � Pα � Sα � zurErzeu-gungvon L � α � � L � β � ! durchWahlderRegelmenge

Pα�g� Sα � λ � Sα � Sβ ��$ Pβ $ � X � aSβ : X � a � Pβ � �

(Im Beweis desInduktionsschritteszeigt manalsogerade,dassRLIN gegenVerket-tung,VereinigungundIterationabgeschlossenist.) �25.19 LEMMA . Zu jederrechtslinearenGrammatikG kannmaneffektiv einennicht-deterministischenendlichenAutomatenM angeben,der die von G erzeugteSpracheerkennt.

BEWEIS. SeidierechtslineareGrammatikG �>� N � T � P� S� gegeben,wobeiwir o.B.d.A.annehmenkonnen,dassG in Chomsky-Normalform ist. Ein nichtdeterministischerendlicherAutomatM �h� T � Z � δ � z0 � E � mit L � M � � L � G� arbeitetwie folgt. Bei Ein-gabew � a1 �� an ”

rat“ M eineAbleitung(25.1)von w in G, wobeiM sichim Zustanddie VariablenXk deraktuellenSatzformzur AbleitungdesRestwortesak � �� an merkt.FindetM solcheineAbleitungvon w, beendetM dieRechnungim akzeptierendenZu-stand. . Formaldefinierenwir Z : � N $ �i. � , z0 : � S, E : �g�j. � (falls λ )� L � G� ) bzw.E : ��i. � S� (falls λ � L � G� ) undδ durch

�;� X � a�(� Y �9� δ : " X � aY � P (25.7)�:� X � a�I� . �K� δ : " X � a � P (25.8)


Zum Nachweisvon L � G� � L � M � zeigtmanzunachstmit Hilfe von (25.7)fur Worterv� w � T ! undVariablenX � N

S !�G

wX " � S� wv�k!�M

� X � v�durchInduktionnach ' w ' , woraussichdann

S !�G

w " � S� w� !�M

�l. � λ �mit Hilfe von (25.8)ergibt. �25.20 LEMMA . Zu jedemnichtdeterministischenendlichenAutomatenkannmanef-fektiv einenaquivalentendeterministischenendlichenAutomatenangeben.

BEWEIS. SeidernichtdeterministischeendlicheAutomatM �� Σ � Z � δ � z0 � E � gegeben.EinendeterministischenendlichenAutomatenM � �>� Σ � Z �� δ �� z�0 � E �M� mit L � M � � L � M �M�erhalt manmit folgenderIdee:M � merktsichnachEinleseneines(Teil-)Wortesw alleM-Zustandein seinemZustand,die M nachEinlesenvon w moglicherweiseerreichthabenkann.Enthalt dieseMengeamEndeeinenM-Endzustand,soakzeptiertM � dieEingabe.Formalist M � wie folgt definiert:

Z � : �g� A : A 8 Z � (d.h.Z � ist diePotenzmengevonZ)

z�0 : �g� z0 �E � : �� A � Z � : A m E )� /0 �

undδ � : Z �nF Σ � Z � ist festgelegt durch

δ � � A � a� �4� z� � Z : L z � A �:�;� z� a�I� z� �K� δ � �Zum Nachweisder Korrektheitder Simulationzeigt manfur Worter v� w � Σ ! durchInduktionnach ' w ' , dass

� z�0 � wv�o!�M # � A � v� " A �� z � Z : � z0 � wv�k!�

M� z� v�p�

gilt. Fur v � λ folgt dannhieraus

w � L � M � � " w � L � M �unterBerucksichtigungdesAkzeptanzmechanismusnichtdeterministischerAutomatenundderDefinition derEndzustandevonM � . �25.21 LEMMA . Zu jedemdeterministischenendlichenAutomatenM kannmaneffek-tiv einenregularenAusdruckangeben,derdievon M erkannteSprachedarstellt.

BEWEIS. SeiderdeterministischeendlicheAutomatM �� Σ � Z � δ � z0 � E � gegeben.UmeinenregularenAusdruckα mit L � M � � L � α � zu konstruieren,zerlegenwir die vonM akzeptierteSprachemit Hilfe von Vereinigungen,Verkettungenund IterationenineinfachereSprachen,die wir durch regulare Ausdruckebeschreiben.Wegen desef-fektivenAbschlussesderKlasseREG derregularenMengengegendieseOperationenerhalt manausdiesenTeilausdruckendanneinenAusdruck,derL � M � beschreibt.


OhneEinschrankungkonnenwir von Z �<� 1 � �� m� undz0� 1 als Startzustand

ausgehen.Fur beliebigeZustandez� z� definierenwir

L � z� z� � �q� w � Σ ! : � z� w�o!�M

� z� � λ � �als die Mengeder Worter, nachderenvollstandigemEinlesenmanvom Zustandz indenZustandz� gelangt.Die von M akzeptierteSprachelasstsichalsendlicheVereini-gungsolcherMengendurch

L � M � � � w � Σ ! : L z � E �:� 1 � w� !�M

� z� λ �:� �� r

zs E

L � 1 � z�darstellen,weshalbesgenugt,dieRegularitatderSprachenL � z� z�M� nachzuweisen.Hier-zuverfeinernwir dieseSprachen,indemwir diezulassigenZwischenzustandebeidemUbergangvonznachz� beschranken.Fur k * m, z� z�i� Z undw � a1 � �� an � Σn (n � 0)definierenwir fur n � 0

� z� λ � !�k

� z� � λ � : " z � z�undfur n � 1

� z� a1 � � � an � !�k

� z� � λ � : " Esgibt z1 � � � � � zn� 1 � Z m � 1 � � �;� � k �mit δ � z� a1 � � z1 �δ � zi � ai � 1 � � zi � 1 fur i � � 1 � � �;� � n 1 2 �B�undδ � zn� 1 � an � � z� �

Hiermit definierenwir dann

Lk� z� z� � : �q� w � Σ ! : � z� w�t!�

k

� z� � λ � � �Lk

� z� z�M� enthalt alsogeradedie Worter w ausL � z� z� � , bei denenwahrenddesEinle-sensvon w (nachdemVerlassendesAnfangszustandesz undvor demErreichendesEndzustandesz� ) nur Zustandez� �=* k durchlaufenwerden.NachWahl von Z gilt alsoinsbesondereL � z� z�M� � Lm

� z� z�M� . Zum Nachweisder Regularitat derSprachenL � z� z�M�genugtesalso,dieRegularitatderSprachenLk

� z� z�M� (fur allez� z�u� Z undk * m) durchInduktionnachk zu zeigen.

Fur k � 0 beobachtenwir, dassL0� z� z�M� nur WorterderLange * 1 enthaltenkann,

also endlichund damit regular ist. Der Grundhierfur ist, dassalle Zustandegroßerals0 sind,alsonur RechnungenderLange * 1 in Fragekommen,danur diesekeineechtenZwischenzustandebesitzen.Fur denInduktionsschrittseik � m gegeben,undnachInduktionsvoraussetzungseienLk

� z� z� � (fur allez� z� � Z) regular. ZumNachweisderRegularitatvonLk � 1

� z� z�M� (fur gegebenesz� z�n� Z) beobachtenwir, dassLk � 1� z� z�M�

durch

Lk � 1� z� z� � � Lk

� z� z� �=$ Lk� z� k . 1� � Lk

� k . 1 � k . 1�;� ! Lk� k . 1 � z� � (25.9)

dargestelltwerdenkann.Ist w namlichin Lk � 1� z� z�M� , sotritt beimEinlesenvon w (be-

ginnendim Zustandz) entwedernie derZustandk . 1 auf,weshalbw � Lk� z� z�M� gilt,

oderwir konnenw zerlegenin w � x1 �� xpy (p � 1), sodassk . 1 alsZwischenzustand


geradenachdemEinlesenderAnfangsstuckex1 � � � xq (1 * q * p) auftritt.Dasbedeutetaber, dassx1 � Lk

� z� k . 1� , x2 � � � � � xp � Lk� k . 1 � k . 1� undy � Lk

� k . 1 � z�M� gilt, alsow einElementvon Lk

� z� k . 1� � Lk� k . 1 � k . 1�;� ! Lk

� k . 1 � z�� ist.Aus (25.9)folgt aberdie Regularitat von Lk � 1

� z� z�M� , dasichdie Sprachemit Hilfevon Vereinigung,VerkettungenundIterationenausdennachInduktionsvoraussetzungregularenSprachenLk

� z� z�M� , Lk� z� k . 1� , Lk

� k . 1 � k . 1� und Lk� k . 1 � z�M� darstellen

lasst. �

Documents

25. Regular¨ e Sprachen · 25 REGULA¨RE SPRACHEN 178 (wobei X Y N;a1 F an T) durch zulassige¨ aqui¨ valente Regeln ersetzt werden. Im alle von Regeln (R1) und (R2) geht man hier