Compilerbau

3. Übungsaufgabe (40 Punkte)

Abgabetermin: 4. Mai 1998 bzw. 7. Mai 1998

Lernziel: DFSA und NFSA verstehen; Akzeptanz verstehen und programmieren können

1. (16 Punkte) Erstellen Sie ein Programm, die ein deterministischer endlicher Automat (DFSA) implementiert zur Erkennung von Zeichenreihen. Der Automat kann als Konstante im Programm vereinbart werden. Das Programm soll eine Zeichenreihe einlesen und feststellen, ob die Zeichenreiche zur Sprache der FSA gehört oder nicht.
2. (je 3 Punkte) Füge jeder der folgenden FSAs in Ihr Programm hinein und bestimmen Sie, welches der Zeichenreihen akzeptiert werden.

   1. 	a	b
      1	2	3
      2	1	2
      <3>	1	3

      Zeichenreihen:
      aaaaa - bbbbb - ababa - babab - abbbb

   2. 	a	b
      1	1	2
      <2>	3	3
      3	2	1

      Zeichenreihen:
      abbab - babba - abbaa - bbaab - abaaa

   3. 	a	b	c
      1	2	3	1
      <2>	1	3	4
      3	2	4	1
      <4>	3	3	2

      Zeichenreihen:
      abc - bcacba - ccca - cbabc - bbbb

3. (je 5 Punkte) Für jeder der folgenden NFSAs, zeichne den Zustandsübergangsdiagramm! Stelle fest, welches der Zeihenreihen akzeptiert werden!

   1. 	a	b
      1	{1,2}	{3}
      <2>	{1}	{2,3}
      3	{1,2}	{1}

      Zeichenreihen:
      aaab - baaab - ababab - baabb - aba

   2. 	a	b	ε
      1	{1}	{3}	{4}
      2	{2}	{1}	{}
      <3>	{1}	{4}	{2}
      <4>	{3}	{2}	{}

      Zeichenreihen:
      abaab - baabb - aabb - bababa - abbb

   3. 	a	b	c	ε
      1	{1,2}	{2}	{1,3}	{}
      2	{3}	{2,3}	{1}	{4}
      <3>	{3,4}	{2}	{2,4}	{1}
      4	{1}	{2}	{3}	{}

      Zeichenreihen:
      abaabc - bacabb - cbaba - ccaacc - babcb

   ---

4. Zusatzaufgabe (10 Punkte) Erstellen Sie ein FSA für einen Getränkeautomat, das mit 10 oder 50 Pfennigstücke oder 1 DM Münzen gefuttert werden kann! Ein Getränk kostet 1 DM. Geben Sie dafür die Tabelle an!