 Reguläre Grammatiken |
Antoshka
Grünschnabel
Dabei seit: 13.02.2016
Beiträge: 2
 |
|
Hallo zusammen,
ich schreibe nächste Woche eine Klausur über die Automatentheorie und es gibt nun eine Sache, die ich nicht verstehe:
Was genau sind reguläre Grammatiken? Wann ist eine Grammatik Regulär und wann nicht?
Wäre super, wenn das jemand an einem beliebigen Beispiel erklären könnte
|
|
13.02.2016 19:38 |
|
|
|
|
Eine reguläre Grammatik ist äquivalent zu einem endlichen Automaten.
Das heißt, du hast nur eine endliche Menge von Zuständen. Daher ist es z.B. nicht möglich, eine beliebige Menge an Klammern zu verarbeiten.
Beispiel: Du kannst einen Automaten konstruieren, der für 3 verschachtelte Klammernpaare prüft, ob die Anordnung zulässig ist. (etwa "{[()]}" als gültig oder "[{(]})" als ungültig erkennen).
Wenn dieser Automat dann aber 4 verschachtelte Klammern kriegt, funktioniert er plötzlich nicht mehr. Man kann mit komplexeren Automaten zwar auch mehr als 3 Klammern prüfen, aber die Anzahl ist endlich.
Was eine reguläre Grammatik kann, ist die Reihenfolge zu prüfen (wenn du keine ')' vor '(' erlauben willst).
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
13.02.2016 21:01 |
|
|
Antoshka
Grünschnabel
Dabei seit: 13.02.2016
Beiträge: 2
|
|
Okay, jetzt verstehe ich es glaub ich
Also heißt das, dass wenn ich einen endlichen Automaten erstellen kann, dann ist das eine reguläre Grammatik und wenn es keinen endlichen Automaten dafür gibt, dann ist das auch keine reguläre Grammatik?
|
|
|
13.02.2016 23:46 |
|
|
|
