Die Mathe-Redaktion - 23.02.2020 18:20 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 540 Gäste und 20 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Konstruktion eines bestimmten Automaten
Druckversion
Druckversion
Autor
Universität/Hochschule J Konstruktion eines bestimmten Automaten
LernenWollen
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2019
Mitteilungen: 67
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-23


Hallo!

Ich bearbeite gerade eine Aufgabe einer älteren Klausur aus dem Modul der Theoretischen Informatik 1.

Gegeben sei folgende Sprache $L$, zu der man einen NFA konstruieren soll:

$L = \Bigl( \Bigl(a^K\Bigr)^* \cup \Bigl((ab)^{K/2}\Bigr)^*\Bigr)^K$

mit $K \in \mathbb{N}$ ist gerade Zahl, $\Sigma = \{a, b\}$, $\epsilon$-Transitionen sind erlaubt.

Die Schwierigkeit, die ich an dieser Aufgabe habe ist, dass ich zwar mit einer geraden Zahl $K$ umgehen könnte, allerdings nicht mit $K/2$.
Das ist kein Kellerautomat oder eine Turingmaschine, die zählen können.

Deswegen fehlt mir eine Idee zum Umgang mit dieser $K,K/2$-Situation.

Vielen Dank für Tipps und Anregungen!

Freundlichste Grüße
LernenWollen




  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2927
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-24


Hallo,

das $K$ ist doch fest, oder? Man muss also nichts zählen, sondern einfach entsprechend viele Kopien desselben Automaten hintereinanderschalten.


[Verschoben aus Forum 'Theoretische Informatik' in Forum 'Formale Sprachen & Automaten' von ligning]


-----------------
⊗ ⊗ ⊗



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2019
Mitteilungen: 67
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-24


Es ist komplizierter. In der Aufgabe steht, man solle einen NFA $A_K$ konstruieren. Sicher ist $K$ fest, aber es ist sehr allgemein gehalten.
Was mich aber am meisten irritiert ist, dass es neben dem $K$ auch ein $K/2$ gibt.
Da das $K$ gerade ist (zählen kann ich ja nicht, ich kann nur Schleifen bauen), ist es egal, ob es 2, 4, 6, 16, 500 oder 274954212 ist.
Aber $K/2$ verhält sich ja so lustig. Mal ist es gerade, mal nicht. Und da müsste ich ja zählen können.

Mich verwirrt das sehr. Ich kann mir einfach nicht erklären, wie das mit einem NFA gehen soll. Das ist auch so eine Aufgabe, bei der klar ist, dass es gehen muss.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2927
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-01-24


Wieso ist es wichtig, ob K/2 gerade ist oder nicht, und wieso musst du deshalb zählen können?  confused

Vielleicht fällt es dir mit diesem Ausdruck leichter:
$\left ( ((aa)^N)^*\cup ((ab)^N)^*\right )^{2N}$



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2019
Mitteilungen: 67
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-01-24


Danke für deine Antwort, aber es fällt mir dadurch nicht leichter. Lass mich das erklären:

Das $N$ kann ich erreichen, indem ich entweder einen Teil des Automaten $N$-mal hintereinanderhänge oder eine Schleife habe.
Ersteres fällt weg, da ich einen Automaten für eine feste, aber eben unbekannte Zahl $K$ baue. Konstruiere ich nun einen NFA $A_{20}$, dann kann er eben nur $K = 20$.

Und wenn ich Schleifen nutze, dann kommt ein neues Problem.
Nehmen wir an, ich gehe $N$-mal durch diesen Teil:
$(aa)$.
Dann muss ich auch dafür sorgen, dass ich genau doppelt so oft
$\left ( ((aa)^N)^*\cup ((ab)^N)^*\right )$
passiere.

Vielleicht stimmt auch etwas nicht mit meinem Verständnis dieses $K$s.
Nehmen wir mal nur den Automaten, der $((aa)^N)^*$ akzeptiert.
Dann habe ich zwei Zustände:
Start- und Endzustand $q_0$ und einen Zustand $q_1$.
Ich habe zwei Transitionen:
$(q_0, a, q_1), (q_1, a, q_0).$

Dann ist $N$ wohl nicht mehr so fest wie gedacht ...
Aber was ist die Alternative? Ich müsste im Vorfeld ein $N$ festlegen. Allerdings muss ich eine Konstruktion für alle $N$ (eigentlich ja $K$, aber für den Moment nebensächlich) schaffen. Also für jeden der unendlich vielen Möglichkeiten.

Ne, ich denke, mein Verständnis liegt betrunken in der Ecke. Je mehr ich drüber nachdenke, desto schlimmer wirds.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2927
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-01-24


2020-01-24 17:07 - LernenWollen in Beitrag No. 4 schreibt:
Das $N$ kann ich erreichen, indem ich entweder einen Teil des Automaten $N$-mal hintereinanderhänge oder eine Schleife habe.
Ersteres fällt weg, da ich einen Automaten für eine feste, aber eben unbekannte Zahl $K$ baue. Konstruiere ich nun einen NFA $A_{20}$, dann kann er eben nur $K = 20$.
Du wirst schon einen Automaten bauen müssen, der von $K$ abhängt. Wie willst du damit sonst eine Sprache erkennen, die von $K$ abhängt?


Und wenn ich Schleifen nutze, dann kommt ein neues Problem.
Nehmen wir an, ich gehe $N$-mal durch diesen Teil:
$(aa)$.
Dann muss ich auch dafür sorgen, dass ich genau doppelt so oft
$\left ( ((aa)^N)^*\cup ((ab)^N)^*\right )$
passiere.
Das geht nicht. Wenn du zu einem vorherigen Zustand zurückkehrst, ist damit auch alles vergessen, was vorher passiert ist (mit Ausnahme davon, dass die Eingabe gelesen wurde, natürlich). Ich glaube, das ist dir eigentlich auch klar, denn dass man nicht zählen kann hat ja genau diesen Grund.


Vielleicht stimmt auch etwas nicht mit meinem Verständnis dieses $K$s.
Nehmen wir mal nur den Automaten, der $((aa)^N)^*$ akzeptiert.
Dann habe ich zwei Zustände:
Start- und Endzustand $q_0$ und einen Zustand $q_1$.
Ich habe zwei Transitionen:
$(q_0, a, q_1), (q_1, a, q_0).$

Dann ist $N$ wohl nicht mehr so fest wie gedacht ...
Aber was ist die Alternative?
Eine Kette von $2N$ $a$-Übergängen zu bauen.


Allerdings muss ich eine Konstruktion für alle $N$ (eigentlich ja $K$, aber für den Moment nebensächlich) schaffen. Also für jeden der unendlich vielen Möglichkeiten.
Genau, du musst eine allgemeine Vorschrift angeben, die für jedes $N$ (bzw. $K$) einen entsprechenden NFA konstruiert.



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2019
Mitteilungen: 67
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-01-24


Eine solche Vorschrift habe ich noch nie gesehen.
Ich kann einen Automaten angeben, wobei die Zustandsmenge ja dann fest ist. Und die Transitionen müssen ja auch dann für jedes $K$ fest sein.

Wie sähe denn eine solche Vorschrift für einen Automaten $A_X$ aus, der die Sprache $L = a^X$ erkennt mit $\Sigma = {a}$ und $X \in \mathbb{N}$?

Für ein bestimmtes $X$ ne leichte Aufgabe. Aber als allgemeine Vorschrift?

$Q = \{q_i ~|~ i \in \mathbb{N}, ~i \leq X\}$,
$\delta = \{(q_i, ~a, ~q_{i ~+~ 1}) ~|~  i \in \mathbb{N}, ~i < X\}$,
Endzustandsmenge $Q_{end} = \{q_X\}$,
Startzustand $q_1$.

Hmmm ... wie umfangreich muss sowas bei der Aufgabe sein? Das ist eine von 10 Aufgaben in 120 Minuten, das kann nicht sein.



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2927
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-01-25


Vielleicht solltest du dann jemanden nach einer Musterlösung fragen.

Wie aufwändig das ganze ist, hängt ja davon ab, wie man den Automaten aufschreibt. Das im Detail auszuformulieren scheint mir nicht unmöglich im Rahmen einer Klausur zu sein -- man braucht ja überhaupt keine Idee, sondern muss nur die Transformation Regex → NFA mechanisch ausführen. Dann hat man eine Zeichnung bzw. Skizze des Automaten, und wenn man muss, kann man sich jetzt irgendein System für die Benennung der Zustände überlegen, das es möglichst einfach macht, die Übergangsrelation aufzuschreiben.



  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2019
Mitteilungen: 67
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-01-25


Danke, das wird dann der sinnvollste Weg sein. Ich werde mich mal um eine Musterlösung bemühen.




  Profil  Quote  Link auf diesen Beitrag Link
LernenWollen hat die Antworten auf ihre/seine Frage gesehen.
LernenWollen hat selbst das Ok-Häkchen gesetzt.
LernenWollen wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]