---
# System prepended metadata

title: TGI Hausaufgabe 8

---

# 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.

![](https://i.imgur.com/h8r38g7.jpg)

**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:

![](https://i.imgur.com/9I9OOC9.jpg)

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:

![](https://i.imgur.com/5E44cyd.jpg)

**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