# TGI Hausaufgabe 8

#### <u>Aufgabe 1</u>
**Automat A:**
Bei diesem Automaten handelt es sich um einen DEA.
Unser Automat akzeptiert nur Wörter in denen mindestens ein b ist
und die Anzahl der b nicht ganzzahlig durch 3 teilbar ist. Die Anzahl
der a ist hierbei egal.


**Zustands-Äquivalenz-Matrix:**

**1.Schritt:** Alle Zustandspaare mit einem Ziel- und einem Nicht-Zielzustand.

| **q1** | X | --- | --- |
| ------ | ------ | ------ | ------ |
| **q2** | X | | **---**|
| **q3** | | X | X |
| | **q0** | **q1** | **q2** |

**2.Schritt:** Plus alle Paare, die eine Transition zu einem X-Paar haben.
$\delta$((q1,q2), b) = (q2,q3)

| **q1** | X | --- | --- |
| ------ | ------ | ------ | ------ |
| **q2** | X | X | **---**|
| **q3** | | X | X |
| | **q0** | **q1** | **q2** |

**3.Schritt:** Alle übriggebliebenen Paare sind äquivalente Zustände, also q0 und q3.
<br><br><br>
**Automat B:**
Bei diesem Automaten handelt es sich um einen NEA.
Bei diesem haben wir folgende Übergangstabelle:
|δ |a |b |
|:---:|:-----:|:-----:|
|q0 |q1 |{q2,q1}|
|q1 |{q1,q2}|{q3,q2}|
|q2 |q0 |q1 |
|q3 |{q3,q2}|∅ |

Nach obiger Konstruktion ergeben sich die Zustandsmenge Q'={q'0,q'1,q'2,q'3,
q'01,q'02,q'03,q'12,q'13,q'23,q'012,q'013,q'023,q'123,q'0123}

|δ |a |b |
|:----:|:----:|:---:|
|q'0 | q'1 |q'12 |
|q'1 |q'12 |q'23 |
|q'2 |q'0 |q'1 |
|q'3 |q'23 |∅ |
|q'01 |q'123 |q'123|
|q'02 |q'01 |q'12 |
|q'03 |q'123 |q'12 |
|q'12 |q'012 |q'123|
|q'13 |q'123 |q'23 |
|q'23 |q'023 |q'1 |
|q'012 |q'012 |q'123|
|q'013 |q'123 |q'123|
|q'023 |q'0123|q'12 |
|q'123 |q'0123|q'123|
|q'0123|q'0123|q'123|
|∅ |∅ |∅ |

Hierbei sind alle die q0 enthalten Endzustände also q'0, q'01, q'02, q'03,
q'012, q'013, q'023, q'0123. Somit würde unser Automat nun so aussehen:


Allerdings sind die Zustände q'2, q'3, q'01, q'02, q'03, q'13, q'013 nicht erreichbar und können deshalb entfernt werden.
Nun würde unser Automat so aussehen:


**1.Schritt:** Alle Zustandspaare mit einem Ziel- und einem Nicht-Zielzustand.

| q1 | X | --- | --- | --- | --- | --- | --- |
| --------- | ------ | ------ | ------- | ------- | -------- | -------- | -------- |
| **q12** | X | | **---** | **---** | **---** | **---** | **---** |
| **q23** | X | | | **---** | **---** | **---** | **---** |
| **q012** | | X | X | X | **---** | **---** | **---** |
| **q023** | | X | X | X | | **---** | **---** |
| **q123** | X | | | | X | X | **---** |
| **q0123** | | X | X | X | | | X |
| | **q0** | **q1** | **q12** | **q23** | **q012** | **q023** | **q123** |

**2.Schritt:** Plus alle Paare, die eine Transition zu einem X-Paar haben.

| q1 | X | --- | --- | --- | --- | --- | --- |
| --------- | ------ | ------ | ------- | ------- | -------- | -------- | -------- |
| **q12** | X | X | **---** | **---** | **---** | **---** | **---** |
| **q23** | X | X | | **---** | **---** | **---** | **---** |
| **q012** | X | X | X | X | **---** | **---** | **---** |
| **q023** | X | X | X | X | | **---** | **---** |
| **q123** | X | X | | | X | X | **---** |
| **q0123** | X | X | X | X | | | X |
| | **q0** | **q1** | **q12** | **q23** | **q012** | **q023** | **q123** |

**3.Schritt:** Plus alle Paare, die jetzt eine Transition zu einem X-Paar haben.

| q1 | X | --- | --- | --- | --- | --- | --- |
| --------- | ------ | ------ | ------- | ------- | -------- | -------- | -------- |
| **q12** | X | X | **---** | **---** | **---** | **---** | **---** |
| **q23** | X | X | X | **---** | **---** | **---** | **---** |
| **q012** | X | X | X | X | **---** | **---** | **---** |
| **q023** | X | X | X | X | | **---** | **---** |
| **q123** | X | X | | X | X | X | **---** |
| **q0123** | X | X | X | X | | | X |
| | **q0** | **q1** | **q12** | **q23** | **q012** | **q023** | **q123** |

**4.Schritt:** Es könnnen keine weiteren Paare markiert werden, damit ist:
q12 = q123,
q012 = q023 = q0123