Konstruktionsvorschrift < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben seien zwei endliche Automaten M1 und M2. Geben Sie eine Konstruktionsvorschrift an, um daraus einen Automaten M3 mit [mm] $L(M3)=L(M1)\cdot [/mm] L(M2)$ zu gewinnen.
Demonstrieren Sie ihre Idee an der Sprache:
$L = [mm] \{w \in \Sigma^{\star}_{\text{Bool}} | w \text{ beginnt mit } 00\} \cdot \{w \in \Sigma^{\star}_{\text{Bool}} | \text{Zahlwert(w)} \% 3 \}$
[/mm]
Sie dürfen hier mit NEA, DEA, oder ϵ-NEA konstruieren. |
Ich hab nun zur linken Sprache gleich mal eine Frage. Ich hab dazu einen NEA konstruiert. Den sieht man hier: http://s7.directupload.net/file/d/2875/x6ll3phq_jpg.htm Ist hier der linke Automat richtig?
Meiner Meinung nach, sollte der rechte modulo3-Automat stimmen. Beim linken Automat (für die Sprache w beginnt mit 00) bin ich mir nicht sicher, da man ja nicht weiß, was mit dem Automaten passiert, wenn am Zustand q1 bspw. eine 1 kommt!
Eine weitere Frage: In der theoretischen Informatik bedeutet ja so ein [mm] $\cdot$ [/mm] eigentlich immer die Konkatenation. Ich gehe mal davon aus, dass bei dieser Aufgabe auch die Konkatenation gemeint ist. Also muss ich, wenn ich beiden "Teilautomaten" entworfen habe, irgendwie die zwei Teilautomaten miteinander konkatenieren. Aber: Wie macht man das? Muss ich hier dann die zwei Teilautomaten miteinader schneiden? Ich hab gelesen, dass gilt: $L1 [mm] \cdot L2=L1L2=\{vw|v\in L1 \cap w\in L2\}$. [/mm] Ist das dann sowas wie der Produkautomat?
Was ist mit Konstruktionsvorschrift gemeint? Ich verstehe darunter einfach einen Automaten, oder? Stimmt das?
Wenn ihr mir helfen würdet, wäre ich sehr dankbar!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:22 Di 01.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
