| |
| Autor |
 Zustände eines Automaten herausfinden |
|
roterWuerfel
Junior 
Dabei seit: 02.10.2023
Mitteilungen: 6
 |  Themenstart: 2023-10-02
|
Ich hatte folgende Aufgabe:
Betrachte die Sprache L = {w ∈ {a, b} ∗ ||w|a > 1 ∧ |w|b < 3}
Man sollte erstmals ohne den Automat aufzuzeichnen bestimmen wie viele Zustände und Endzustände dieser haben könnte. In Lösungen steht 12 Zustände und 4 Endzustände.
Das einzige was ich mit dieser Sprache anfangen kann ist ein paar mögliche Wörter aufzuschreiben: aabb, abab, baab, bbaa, baba, abba. Wie kommt man auf diese Lösung?
Gibt es irgendeine Formel wie man das nur mit der gegebenen Sprachen also ohne Automat bestimmen kann?
|
 Profil
|
tactac
Senior 
Dabei seit: 15.10.2014
Mitteilungen: 2961
 | Beitrag No.1, eingetragen 2023-10-02
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
Die Zustände werden dafür benutzt, die as bzw. bs im Wort zu zählen.
Für die as sind die relevanten Anzahlen: $0,1,\geq 2$; für die bs $0,1,2,\geq 3$. Diese werden unabhängig voneinander gezählt. Daher ergeben sich $3 \cdot 4 = 12$ Zustände. Tatsächlich könnte man aber auch die Zustände, in denen der Automat schon zu viele b gesehen hat, zusammenfassen. Dies ergäbe 10 Zustände.
Akzeptierende Zustände müsste es m.E. 3 geben, nicht 4. \(\endgroup\)
|
Profil
|
Kitaktus
Senior 
Dabei seit: 11.09.2008
Mitteilungen: 7272
Wohnort: Niedersachsen
| Beitrag No.2, eingetragen 2023-10-03
|
\quoteon(2023-10-02 13:44 - tactac in Beitrag No. 1)
Akzeptierende Zustände müsste es m.E. 3 geben, nicht 4.
\quoteoff
Nimmt man noch einen nicht-akzeptierenden Endzustand dazu, ist man dann wieder bei 4.
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2961
| Beitrag No.3, eingetragen 2023-10-03
|
\quoteon(2023-10-03 16:33 - Kitaktus in Beitrag No. 2)
\quoteon(2023-10-02 13:44 - tactac in Beitrag No. 1)
Akzeptierende Zustände müsste es m.E. 3 geben, nicht 4.
\quoteoff
Nimmt man noch einen nicht-akzeptierenden Endzustand dazu, ist man dann wieder bei 4.
\quoteoff
Für mich sind "Endzustand" und "akzeptierender Zustand" im Kontext endlicher Automaten synonym. Für den TS vermutlich auch.
|
Profil
|
roterWuerfel
Junior
Dabei seit: 02.10.2023
Mitteilungen: 6
| Beitrag No.4, vom Themenstarter, eingetragen 2023-10-04
|
Vielen Dank für eure Antworten. Ich denke ich verstehe das ein bisschen, aber mir ist immer noch nicht klar wie du auf die Rechnung 3*4 kommst ... könntest du mir das vielleicht erklären? Oder gibt es dazu eine Formel?
|
Profil
|
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 7272
Wohnort: Niedersachsen
| Beitrag No.5, eingetragen 2023-10-04
|
Da hast Du wahrscheinlich recht. Ich habe mich durch die unterschiedlichen Begriffe irritieren lassen.
[Die Antwort wurde nach Beitrag No.3 begonnen.]
|
Profil
|
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 7272
Wohnort: Niedersachsen
| Beitrag No.6, eingetragen 2023-10-04
|
Das steht in Beitrag #1. Eine naheliegende Umsetzung sieht so aus:
1) Bilde drei "a-Klassen" je nach Anzahl der a's, nämlich "kein a", "ein a" und "mehr als ein a".
2) Bilde vier "b-Klassen" je nach Anzahl der b's, nämlich "kein b", "ein b", "zwei b's" und "drei oder mehr b".
3) Für jede Kombination aus a- und b-Klasse nimm einen Zustand.
Dann bist Du mit den 3*4=12 Zuständen in der Lage alle relevanten(*) Informationen über die bisher gezählten a's und b's zu speichern und kannst am Ende anhand des Zustands genau sagen, ob die Bedingung erfüllt wurde, oder nicht.
Das ist vermutlich der naheliegendste Weg, um auf 12 Zustände zu kommen. Da sich das Problem aber auch mit weniger Zuständen lösen lässt, sind auch andere Anzahlen oder Zuordnungen möglich.
(*) Das damit alle relevanten Fälle abgedeckt sind, muss man sich anhand der Fragestellung überlegen.
|
Profil
|
roterWuerfel
Junior 
Dabei seit: 02.10.2023
Mitteilungen: 6
| Beitrag No.7, vom Themenstarter, eingetragen 2023-10-05
|
Ok, das Aufschreiben der Klassen hilft mir weiter! Vielen Dank.
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2961
| Beitrag No.8, eingetragen 2023-10-06
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
So sähe übrigens die Variante mit einem zusammengefassten Zustand für "zu viele b" graphisch aus:
$
\tikzset{
->,
node distance=3cm,
every state/.style={thick, fill=gray!10},
initial text=$ $,
}
\begin{tikzpicture}
\node[state, initial] (00) {00};
\node[state,right of=00] (01) {01};
\node[state,right of=01] (02) {02};
\node[state,below of=00] (10) {10};
\node[state,right of=10] (11) {11};
\node[state,right of=11] (12) {12};
\node[state,right of=12] (?3) {?3};
\node[state,below of=10, accepting] (20) {20};
\node[state,right of=20, accepting] (21) {21};
\node[state,right of=21, accepting] (22) {22};
\draw
(?3) edge[loop right] node{a,b} (?3)
(00) edge[left] node{a} (10)
(10) edge[left] node{a} (20)
(01) edge[left] node{a} (11)
(11) edge[left] node{a} (21)
(02) edge[left] node{a} (12)
(12) edge[left] node{a} (22)
(20) edge[loop below] node{a} (20)
(21) edge[loop below] node{a} (21)
(22) edge[loop below] node{a} (22)
(00) edge[above] node{b} (01)
(01) edge[above] node{b} (02)
(10) edge[above] node{b} (11)
(11) edge[above] node{b} (12)
(20) edge[above] node{b} (21)
(21) edge[above] node{b} (22)
(02) edge[above right] node{b} (?3)
(12) edge[above] node{b} (?3)
(22) edge[below right] node{b} (?3)
;
\end{tikzpicture}
$\(\endgroup\)
|
Profil
|
roterWuerfel
Junior
Dabei seit: 02.10.2023
Mitteilungen: 6
| Beitrag No.9, vom Themenstarter, eingetragen 2023-10-10
|
Ok, super das ist noch besser fürs Verständnis! Vielen Dank für den Automaten.
|
Profil
|
| roterWuerfel hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
