Einführung in die Computerlinguistik

Übung 5

Jan Hendrik Dithmar

Matrikelnummer 2031259

Übung 5  Dithmar (2031259)

Aufgabe 5.1

(a)

Hier die Variante, bei der führende Nullen zulässig sind:

1  2 0,2,4,6,8 0,...,9

Hier die Variante, bei der führende Nullen nicht zulässig sind:

1  2  3 1,...,9  0,2,4,6,8 2,4,6,8 0,...,9

(b)

Die Idee ist die folgende: Eine Zahl ist durch 4 teilbar, wenn ihre vorletzte Stelle gerade und ihre letzte Stelle durch 4 teilbar ist. Außerdem ist eine Zahl durch 4 teilbar, wenn ihre vorletzte Stelle ungerade und ihre letzte Stelle durch 4 modulo 2 teilbar ist.

1  2  3 4  5 0,2,4,6,8  0,4,8 2,6 1,3,5,7,9 0,...,9

(c)

Ist eine Zahl durch 3 teilbar, so ist auch ihre Quersumme durch 3 teilbar. Teilt man die letzte Ziffer durch 3, so muss Rest 0 herauskommen. Die Zustände des Automaten repräsentieren also den jeweiligen Rest. Die Frage ist nun: In welche Restklasse ”rutscht“ man bei welcher Ziffer am Ende? Dies muss man im Automaten entsprechend berücksichtigen und fertig ;-)

0  1  2 {0,3,6,9}  {0,3,6,9}  {0,3,6,9} {2,5,8} {1,4,7} {1,4,7}  {1,4,7} {2,5,8}  {2,5,8}

Übung 5  Dithmar (2031259)

Aufgabe 5.2

1. Schritt: Mehrsymbolkanten entfernen

1  1a  2  2a  3 4  5  6 t  ε t ε  e  n e  t s t  ε

2. Schritt: ε-Kanten entfernen

1  1a  2  2a  3 4  5  6 t t  e  n e  t s t  t es

3. Schritt: Konstruktion des Potenzautomaten

{1}  {1a,3,4}  {2,5} {2a}  {3} {5}  {6} e  nt s  e s  t t

Aufgabe 5.3

(a)

Der Automat akzeptiert beliebige Zeichenketten aus a’s und b’s, wobei die Anzahl der a’s keine Rolle spielt, b’s jedoch nur in Blöcken mit gerader Anzahl vorkommen dürfen. Das Wort darf nicht mit b beginnen, es dürfen keine b’s am Ende stehen und nach einem Block aus bb müssen mindestens 2 a’s oder kein a kommen.

(b)

1. Schritt: Mehrsymbolkanten entfernen

1  23  2a a  aa  b b ε

2. Schritt: ε-Kanten entfernen

1  23  2a a  aa  b b b b

3. Schritt: Konstruktion des Potenzautomaten

{1}  {1,2}  {2a} {2,3} a  a a  b b b