Upload
halona
View
31
Download
0
Embed Size (px)
DESCRIPTION
Lösung 7.2Reguläre Ausdrücke. Geben Sie reguläre Ausdrücke für Integerliterale:[1-9][0-9]* bzw. (1|2|3|4|5|6|7|8|9)(o|1|2|3|4|5|6|7|8|9)* while, function, ifwhile usw. bzw. ‘w‘‘h‘‘i‘‘l‘‘e‘ usw. Geben Sie einen regulären Ausdruck zu folgenden Sprachen an: - PowerPoint PPT Presentation
Citation preview
Lösung 7.2 Reguläre Ausdrücke
1. Geben Sie reguläre Ausdrücke füra) Integerliterale: [1-9][0-9]* bzw. (1|2|3|4|5|6|7|8|9)(o|1|2|3|4|5|6|7|
8|9)*b) while, function, if while usw. bzw. ‘w‘‘h‘‘i‘‘l‘‘e‘ usw.
2. Geben Sie einen regulären Ausdruck zu folgenden Sprachen an:a) Alle Folgen von Großbuchstaben, die jeden Vokal genau einmal in
alphabetischer Reihenfolge enthält:KONS = [B-DF-HJ-NP-TV-Z]{KONS}A{KONS}E{KONS}I{KONS}O{KONS}U{KONS}
b) Alle Dualziffernfolgen, die „001“ nicht als Teilfolge enthalten(0?1+)*0*
2. Welche Sprachen sind durch die folgenden regulären Ausdrücke definiert ?a) (0?|1*)* alle Binärzahlen, denn (0|1) ist Teilmenge von (0?|
1*)b) (0|1)*0(0|1)(0|1) alle Binärzahlfolgen, bei denen die drittletzte Ziffer
existiert und 0 istc) /\*((\*[^/])|[\*])*\*/ „wohlgeformte“ C-Kommentare
Lösung 7.3 Grammatiken
1. gegeben ist folgende Grammatik G:G = { N,T,P,S }, N = { A,B,C,S }, T = { a,b,c },P = { S:=ABC, A:=ABA, C:=CBC, A:=a, B:=b, C:=c }
a) Die Grammatik ist kontextfrei, da auf der linken Seite aller Regeln genau ein Nichtterminalsymbol steht
b) Beweis durch Ableitung :S ABC ABABC ABABABC ABABABCBC ... : abababcbc
c) Es gibt keine Regel, die ein b vor ein a produziert, daher ist b2a2c3 L(G), denn in b2a2c3 ist ein b vor einem a.
d) (ab)+c(bc)*e) Da die Grammatik G kontextfrei ist die Sprache vom Chomsky-Typ-2. Da
sich die Sprache auch als regulären Ausdruck darstellen lässt, ist die Sprache sogar Chomsky-Typ 3.
f) Ja, denn jede Chomsky-Typ2 bzw. 3 Sprache ist auch vom Chomsky-Typ0