ÜBUNGEN von MAC 1 – ALF (Thema 2) Kurs 2010/2011

ÜBUNGEN zum THEMA 2: Reguläre Sprachen

Über AFDs (deterministische endliche Automaten):

1. Begründe die Wahrhaftigkeit oder Falschheit der folgenden Aussage, indem du dich auf die ...
Theorie, die im Unterricht behandelt wurde. Wenn M = (Q,Σ,δ, q0, F) ist ein deterministischer endlicher Automat
völlig spezifiziert mit F = Q, dann L(M) = Σ.

2. Seem M = (Q,Σ,δ, q0, F) un AFD con Q = {q0,q1,q2},Σ= {a,b}, F = {q2} und die Funktion
der Übergang

δ a b
q0 q0 q1

q1 q2 q1

q2 q2 q0

a) Zeichne den Automaten M

b) Zeichne die Berechnungen von M, die die Wörter abaa, bbbabb, bababa verarbeiten.

bbbaa
c) Welche Wörter aus den in (b) verarbeiteten werden von M akzeptiert?

3. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los
nächsten Automaten, die die Rechnungen verarbeiten. Bestimme welche
von ihnen sind vollständig spezifiziert. Wüsstest du, welche Sprache akzeptiert wird?
Für jeden von ihnen?
a) a b) eine
b
a b
b a
a

b
ein
b
a,b
a,b

Seite 1
ÜBUNGEN zu MAC 1 – ALF (Thema 2) Kurs 2010/2011

c) a b a,b

b a

d b a e) b a

ein b a b
b a b a

a,b a,b

f) g) b a
a b ein

ein ein b b
b ein a b a
b

b a
ein

4. Konstruiere AFDs, die jede der folgenden definierten Sprachen akzeptieren

über das Alphabet Σ= {a,b}:

a ) L = {xΣ* : die Länge von x ist durch 3 teilbar}

b ) L = {xΣ*:abano ist ein Teilwort von x}
c ) L = {xΣ* :x beginnt mit ay endet mit ab}
d ) L = {xΣ* : x hat eine gerade Anzahl von a's und eine gerade Anzahl von b's }
e ) L = {xΣ* :x hat drei aufeinanderfolgende a's}
f ) L = {xΣ* : jede Erscheinung des Teilworts 'aba' in x, wird entweder gefolgt von
bb, o steht am Ende des Wortes }
g ) L = {xΣ* : sixempieza porano contiene la subpalabraaay sixempieza
porbenthält das Unterwort aa}
h ) L = {xΣ* :x hat eine gerade Anzahl von Vorkommen der Zeichenkette ab}
i ) L = {xΣ* :abes Subwort dexsi und nur sibaes Subwort dex}
j ) L = {xΣ* :x ist gebildet aus der Verkettung einer beliebigen Zahl
R
de Ketten der Formayy, mit |y|=2}
k ) L = {xΣ* :x enthält kein Präfix, in dem der Unterschied zwischen dem
Die Anzahl der a's und b's sei größer als drei (zu Gunsten von jemandem)

Seite 2
ÜBUNGEN von MAC 1 – ALF (Thema 2) Kurs 2010/2011

5. (Sonderübung) Baue einen AFD, der die folgende Sprache akzeptiert:

L = {x{a,b}* : x enthält nicht das Teilwort bab und endet nicht mit aba}

6. (SonderübungDemonstriere, dass das Konzept der Sprache, das von einem AFD akzeptiert wird
es hängt vom spezifischen Alphabet ab (solange es mindestens die enthält
Symbole involviert). Das heißt, beweisen Sie, dass:

SiΣ* L y∏ Σ, dann existiert ein AFD über dem Alphabet Σ, das akzeptiert
L ist genau dann, wenn es einen anderen AFD über dem Alphabet ∏ gibt, der L akzeptiert.

Über AFNDs (nichtdeterministische endliche Automaten):

7. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los
folgenden nichtdeterministischen Automaten, alle Berechnungen zeigend, die sie
Prozessieren. Wüsstest du, welche Sprache jeweils akzeptiert wird?

a) b b
a a

b b
b) b b c) ein
a
b

a a b
a a
b

8. Bauen Sie AFNDs, die die folgenden Sprachen über dem Alphabet akzeptieren
Σ= {a,b,c}

a) L = {xΣ* :x hat ein Paar von a's, die durch eine Kette von Symbolen getrennt sind}
von Länge 4*i, mit i≥0 }
b)L = {xΣ* : |x|≥5 und das fünfte Symbol von hinten ist a}
c)L = {xΣ* : niaanibbson Unterzeichenfolgen dex}
d)L = {xΣ* :x hat abybacomo als Teilzeichenfolge }

e) L = {xΣ* :ccces sufijo dexy en ninguna otra posición dexpueden

finde zwei aufeinanderfolgende gleiche Symbole }

Seite 3
EJERCICIOS von MAC 1 – ALF (Thema 2) Kurs 2010/2011

f ) L = {xΣ* :xtiene drei gleiche Symbole hintereinander}

g ) L = {xΣ* : die Symbole an Positionen, die Vielfache von drei sind, sind c's }

9. (Sonderübung) Baue einen nicht-deterministischen endlichen Automaten (AFND), der die folgende Sprache akzeptiert L
{x{a,b,c}* :x beginnt und endet mit ay zwischen jedem Auftreten von ay der
nächste gibt es eine gerade Zahl deb's oder eine ungerade Zahl c's }

10.(Sonderübung) Wie viele deterministische endliche Automaten mit zwei Zuständen gibt es?
Können sie über dem Alphabet {0,1} aufgebaut werden? Akzeptieren sie alle Sprachen?
verschiedene? Und wie viele von ihnen sind vollständig spezifiziert? Und was ist, wenn wir bauen
nichtdeterministische endliche Automaten?

[Link] die reguläre Sprache L =

x a{a,b}*: |x| mod2 {
b = 1 |x|mod3 = 0 aba
es subpalabra de x }. Sigue los pasos que se te indican a continuaciónsin
zu keinem Zeitpunkt den angegebenen endlichen Automaten konstruieren:

a) Angenommen, du möchtest einen endlichen Automaten M bauen, der L erkennt.

Gib an, wie viele Zustände M hätte und erkläre warum. Zähle diese auf.
Zustände, die erklären, wofür jeder von ihnen in deinem Aufbau dient.
Gib an, was der Anfangszustand und was die Endzustände wären.
b)Wähle drei beliebige Staaten aus und gib an, welche ihre Übergänge wären und a
welche Staaten uns führen würden.

c) Rekonstruieren Sie die Berechnungen, die mit den Wörtern aababbybabab verbunden sind.

Über GRs (reguläre Grammatiken) und GLs (lineare Grammatiken):

12. Konstruiere reguläre oder rechtslineare Grammatiken, die jedes von

die folgenden Sprachen über dem Terminalalphabet Σ= {a,b,c}

a) {xΣ* : |x|einmod 2 = 0 }
b){xΣ* :x beginnt mit ay und enthält das Teilwort bbb}
c){xΣ* :x enthält keine drei aufeinanderfolgende b's }

d){xΣ* : |x| ein+ |x|bmod 3 = 0 }

e) {xΣ* :x enthält die Unterwörter aa, bb, ycc}
f) {xΣ* :x enthält nicht die Teilwörter abaniaca}
g){xΣ* : Jede Erscheinung von aenxes wird von b oder gefolgt von c}
h){xΣ* :x enthält keine Vorkommen der Teilzeichenfolge a nach der
letzte Erscheinung des Symbols}
i) {xΣ* :x enthält zwei durch eine ungerade Anzahl von Symbolen getrennte}

S. 4
ÜBUNGEN von MAC 1 – ALF (Thema 2) Kurs 2010/2011

j) {xΣ* : x enthält das Teilwort "ab" aber nicht das Teilwort "aba"}
Von ihnen, sag mir, welche regulär und welche linear sind. Transformiere die
lineare in reguläre.

13.(Sonderübung) Sei G=(N,Σ, P, S) eine rechtslineare Grammatik mit

{S,A,B}ε,aaA,abaS,
bbab,aSba, Baaab,abAS,abBAbSb.

a ) Welche von ihnen könnten sentenzielle Formen von G sein?

b) Beschreiben Sie die allgemeine Struktur einer Satzform von G.
c ) Zeige durch Induktion, dass die Satzformen von G nicht sein können
abweichend von dem im vorherigen Abschnitt beschriebenen.

14. (Sonderübung) Eine rechtsquasi-reguläre Grammatik wird definiert als

Eine Grammatik G = (N, Σ, P, S), wobei die Regeln von P einer der folgenden entsprechen
3 folgende Formen: A→ ε, A →aB, A →a, mit A,B N,aΣ. Betrachte das
nächstes Algorithmus:

G = (N, Σ, P, S) quasi-regelmäßige Grammatik rechts

Ausgang: INCOGNITA
Verfahren: INCOGNITA = ( N1Σ,δ, S, F) wo
N1= N {Z}
F = {Z} A→ ε P
Bδ(A,a) A→aB P
Zδ(A,a) A→aP

a) Wenden Sie den Algorithmus auf die folgende Grammatik an: G=({S,A,B}, {a,b,c}, P, S) wobei P
der Satz von Produktionen
S→aA |aB A→bA | b B→cB |c

b) Zu welchem Modell gehört INCÓGNITA? Begründe deine Antwort.

c) Rechtfertige die folgende Aussage: „ Jede Sprache, die von einer Grammatik erzeugt wird
regulär (a derecha) kann durch eine fast reguläre Grammatik erzeugt werden (a
rechts) und umgekehrt.

Seite 5
ÜBUNGEN von MAC 1 – ALF (Thema 2) Kurs 2010/2011

Über ERs (reguläre Ausdrücke):

15. Sind die folgenden Aussagen wahr oder nicht:

a ) baaL(a*b*a*b*) b ) L(b*a*)∩L(a*b*) = L(a*b*)

c ) L(a*b*)∩L(c*d*) = d ) abcdL((a(cd)*b)*)
e) Die regulären Ausdrücke α=εyβ=(ε )* ihre Entsprechungen.

16. Für die folgenden regulären Ausdrücke, schreibe alle Wörter der Länge
menor oder gleich sechs gehören zur Sprache, die sie generieren, und beschreiben diese
Sprache in jedem Fall:

a) (10)* (01)* b ) (10 01)*

c ) (11 0)*(00 1)* d ) (1 01 001)*( ε 0 00)
e ) [00 11(01 10)(00 11)*(01 10)]*

[Link] Σ ={a,b}. Schreibe reguläre Ausdrücke für die folgenden Sprachen:

a ) Ketten mit mindestens drei a's

b ) Ketten mit höchstens drei a's
c ) Ketten mit einer Zahl, die durch 3 teilbar ist
d ) Zeichenfolgen mit mindestens einer Erscheinung der Teilzeichenfolge aaa

e) Ketten, in denen die Laschens mindestens zu dritt gruppiert sind.

[Link] Σ {a,b}. Baue einen regulären Ausdruck für die Sprache, die durch die gebildet wird
Cadenas, die die Subkette aaa nicht enthalten. Zuerst muss der AFD erstellt werden.
die GRD daraus erhalten und die entsprechenden Gleichungen lösen,
Zur regulären Ausdruck gelangen.

19.(Sonderübung) Sei Σ {a,b}. Baue einen regulären Ausdruck dafür

Sprache, die aus den Zeichenfolgen besteht, die genau eine Vorkommen von enthalten
Die Teilzeichenketteaaa. Zuerst muss der AFD erstellt werden, um daraus die GRD zu erhalten.
y, indem die entsprechenden Gleichungen gelöst werden, zur regulären Ausdruck gelangen.

Seite 6
EJERCICIOS von MAC 1 – ALF (Thema 2) Kurs 2010/2011

[Link] Sie reguläre Ausdrücke, um die folgenden Sprachen darzustellen:

a ) {w{a,b}* : wacaba enab}

b ) {w{a,b}*: |w|a ≠1} .
c ) {w{a,b}* : wtiene un número par dea’s y termina porab}
d ) {w{1,0}* : w enthält nicht 101 als Unterwort }
e ) {w{1,0}* : w beginnt mit 101 und endet mit 101}
f ) {w{a,b,c}* : zwischen jeder Dosa's dewhay eine Zahl dec's, die ein Vielfaches von 3 ist}

[Link] der induktiven Definition von regulären Ausdrücken besagt die Regel, dass
ε Es ist ein regulärer Ausdruck, der entfernt werden kann, da mit den übrigen Regeln
Es ist möglich, einen Ausdruck α zu konstruieren, sodass L(α) = {ε}. Warum?

Über äquivalente ERs zu Automaten:

22. Konstruiere äquivalente reguläre Ausdrücke zu den folgenden AF's:

a b b a,b
ein

b ein
b
a b
a
b
a

Über äquivalente ERs zu Grammatiken:

[Link] reguläre Ausdrücke auf, die den linearen Grammatiken entsprechen.

rechts, deren Produktionsregeln im Folgenden aufgeführt sind:

a) S→aS |bS |abaA |ababaB |abababaC |abababa

A→aA |bA |abaB |ababaC |ababa
B→aB |bB |abaC |aba
C→aC |bC |a|b
b)S→a|aA|bB
A→b|bA
B→a|aA|aC
C→b|bA|aD
D→aC |bD

Seite 7
EJERCICIOS von MAC 1 – ALF (Thema 2) Kurs 2010/2011

Theoretische Übungen über ERs:

24. (Sonderübung) Angenommen, es ist bereits gezeigt, dass für beliebige

Reguläre Ausdrücke α, ..., α, β,1 ..., β erfüllen
n 1 die Bedingung,
n dass :
i ) (α1α 2...αn)* = (α1*α2*...αn*)*
ii ) (α1α 2...αn) (β1β 2...βm) =α1β 1α 1β 2...α1β mα 2β 1
...αnβ 1...αnβ m
Es wird gesagt, dass ein regulärer Ausdruck in disjunktiver Normalform ist, wenn er die
formaα1α 2...α, mit n≥1
n und α, 1 ..., n α sind reguläre Ausdrücke in den
dass das Symbol " " nicht erscheint.

a ) Verwenden Sie die vorherigen Ergebnisse i) yii) zeigen Sie, dass für alle
regulärer Ausdruck α Gibt es eine andere Entsprechung?α ) in normaler Form
Disyuntiva.
b ) Schreibe die disjunktive Normalform der folgenden Ausdrücke
regelmäßig
(ε (0 1)*100)0*
((10*01*) (00*11*))*

[Link] α eine beliebige reguläre Ausdruck:

a ) Entwickle einen rekursiven Algorithmus, um zu entscheiden, ob α es entspricht der

regulärer Ausdruck .
b ) Beschreiben Sie einen anderen Algorithmus, um aus zu erhalten α ein weiteres reguläres Ausdruck

äquivalenteinvak(α )que, oder enthält nicht das Teilmuster , o es

genau der reguläre Ausdruck (unvermeidlich wenn α es entspricht
).
c ) Wenden Sie den im Abschnitt (b) erstellten Algorithmus auf den regulären Ausdruck an:
(1(11)*)*(0 0 01)*( (1 0)*10) .

[Link]αuna reguläre Ausdruck, der keine Vorkommen von der enthält

Subexpression
a ) Entwickle einen rekursiven Algorithmus, um zu entscheiden, ob das leere Wort dazugehört oder
nein ein L(α).
b ) Beschreiben Sie einen anderen Algorithmus, um aus zu erhalten α ein weiterer regulärer Ausdruck

äquivalentesineps( ), dasαweiterhin keine Auftritte von enthalten ist , und dass

ε
hat die Form ,βóβ ε, wo eine reguläre Ausdruck, der nicht
enthält Erscheinungen von ε (d.h. ensineps(α )Wir entfernen alle die
Erscheinungen vonε außer einer, falls es unbedingt notwendig ist

Seite 8
EJERCICIOS von MAC 1 – ALF (Thema 2) Kurs 2010/2011

um die Äquivalenz aufrechtzuerhalten).

c ) Wende den gefundenen Algorithmus auf den regulären Ausdruck (((1 ε )*ε )
01)* ε 1 ε (01) ε ε) ε
(10* .
d ) Angenommen, in der Definition des regulären Ausdrucks werden ...
yε
das sind reguläre
die Klauseln, die sicherstellen, dass Ausdrücke. Im Licht
Von den Ergebnissen dieser Übung und der vorhergehenden, welche wären die
Reguläre Sprachen, die nicht durch diese dargestellt werden könnten? Und wenn
Nehmen wir nur eine der Klauseln heraus?

Über die ε-AFNDs und ihre Beziehung zu den ERs:

[Link] ε-AFNDs, die die folgenden Sprachen akzeptieren über Σ {a, b, c}

a ) L = { xΣ* : die Vorkommen von a dürfen nicht auf c folgen, die
Aparitionen dürfen nicht gefolgt werden von, und die Apparitionen sagen
können nicht hintereinander gehen deb}

b ) L = {xΣ* :x darf keine a an einer späteren Position haben}

Eine byxno enthält isolierte}
c ) L = {xΣ* :x besteht aus einer oder mehreren Gruppen von a's, die durch
Ketten von 1, 2 oder 3b's }
d ) L = {xΣ* :x kann als Verkettung von drei zerlegt werden
subpalabrasy,zywcumpliendo dass in jeder gruppe dea's hat
längliche gerade, jede Gruppe von Debs hat eine gerade Länge und jede Gruppe
dec's hat eine gerade Länge }

[Link] endliche Automaten, die die durch die angegebenen Sprachen darstellten erkennen.
folgende reguläre Ausdrücke:
a ) a*bb*(a b)ab* b ) b((aab*a4)b)*a
+ b*)+
c ) (a b*a + d ) (((b*a)*a)*a)*a
2 3 4 4
e ) (a)*(b)*(c)*(a)*(b)*(c)* 3 2

29. (Sonderübung) a) Konstruiere einen Automaten, M, der alle abweist.

Wörter mit ungerader Länge, die die letzten beiden Symbole gleich haben. Muss
akzeptieren, zum Beispiel, die Wörterabaa,a,abay ablehnenabb,babbbaaaa.
Du kannst es direkt bauen (mit den entsprechenden Erklärungen) oder es erhalten.
durch den nächsten Abschnitt mithilfe eines Transformationsalgorithmus.

Seite 9
ÜBUNGEN zu MAC 1 – ALF (Thema 2) Kurs 2010/2011

b) Entwerfen Sie einen regulären Ausdruck, der dieselbe Sprache wie im Abschnitt erzeugt.

anterior. Sie können sie direkt entwerfen (mit den entsprechenden Erklärungen) u
Sie aus dem vorherigen Abschnitt durch einen Transformationsalgorithmus erhalten.

Über Äquivalenzen zwischen Automaten:

30. Baue AFDs äquivalent zu den folgenden AFNDs:

a ) ({ q0, q1, q2, q301, q0, { q3} )

b ) ({ q0, q1, q2, q3}, {0,1},δ2, q01,q3} )
δ1 0 1 δ2 0 1
q0 q0,q1 q0 q0 q1,q3 q1
q1 q2 q2 q1 q2 q1,q2
q2 q3 - q2 q3 q0
q3 q3 q3 q3 - q0

31. Baue die Äquivalente von AFD zu den folgenden ε-AFNDs:

ein
ein
a
b
ε b ε

a
ε
b ε ε
b a ε

a ε eine
a
a ε a
a ε

a
b b

Seite 10
ÜBUNGEN von MAC 1 – ALF (Thema 2) Kurs 2010/2011

[Link] the following finite automata, construct the minimum finite automaton.
entsprechend jedem von ihnen:
b

a a q2
q0 q1

b
b b ein

q3 a ein q5
q4

a
b

q0
1 0

q1 q2

1 0 1 0

1
q3 q4 q5 q6

1,0 0 1 1,0

[Link] el lenguaje L = Σ {a, b}.

{a100+3ibj: i ‚ j≥0} definiert über das Alphabet
a) Zeige, dass L regulär ist, indem du einen regulären α dass esgibst.
Ausdruck

bezeichnen.
b) Beschreibe, wie ein vollständig spezifiziertes AFD M aussehen würde, α.
das dem entspricht
Strebe danach, dass es der minimale Automat ist. Nimm einen beliebigen Zustand von M, und

prüfen Sie, dass es nicht äquivalent/indistinguishable zu einem der anderen ist

Zustände.
Hinweis: Es ist weder notwendig noch sinnvoll, dass du die Algorithmen anwendest.
Transformation oder Minimierung. Tatsächlich ist es nicht notwendig, dass du schreibst das

vollständiger Automat M.

[Link] wir an, dir werden zwei reguläre Ausdrücke α und β gegeben, und man bittet dich, dass

prüfen Sie, ob sie gleichwertig sind oder nicht. Erklären Sie den Prozess, den Sie befolgen würden, um

es lösen.

Seite 11
EJERCICIOS von MAC 1 – ALF (Thema 2) Kurs 2010/2011

35. Überprüfen Sie, ob die folgenden Aussagen wahr oder falsch sind, und begründen Sie Ihre Antwort.
kurze, aber überzeugende Form.

a) Wir haben einen AFD über das Alphabet {a,b}, der zwei Nichtzustände enthält.
finale, p und q, mit den folgenden Übergängen:
a b
p p q
q p q
Ohne den Rest des Automaten zu kennen, können wir sicher sagen, dass diese Zustände sind
notwendigerweise ununterscheidbar.
b) Wenn M Σ,=δ, q(Q,
0, F) ist der äquivalente minimale Automat zum AFD, N = (P,
Σ, γ, p0, G), die Mächtigkeit von F und G muss gleich sein.

36. Zeige, dass sie über dem Alphabet Σ = {a, b} nicht regulär sind:

a ) {wwΣ: * w es ist das Wort, das entsteht, wenn man jede Vorkommen von enwdea ändert

porby viceversa
b ) {wΣ:w=w*R|w|ein= |w|b}
c ) Invalid inputnbmm≤n≤2*m
d ) {aichbjakj = max(i,k) }
e ) {aichbjak: i, j, k >0 (i≤j j ≥k i = k) }
f ) Ungültige Eingabeichbjak: i, j, k >0 (i = j i = k j = k) }
g ){wΣ:wtiene * al menos un prefijo con másb's quea's }

37. Betrachtet das Alphabet {M,D,C,L,X,V,I} und die Sprache der Zahlen
Romano. Beweisen Sie, dass es sich um eine reguläre Sprache handelt, indem Sie einen Automaten konstruieren.

fertig mit leeren Übergängen, die es erkennen kann. Denk daran, dass zum Beispiel, VIII
es ist keine römische Zahl, und wir müssen stattdessen IX schreiben. Kann
Es ist nützlich, den regulären Ausdruck zu erstellen und dann den ε-AFND.
entsprechend.

Seite 12