Reguläre Grammatiken |
| 13.02.2016, 19:38 | Auf diesen Beitrag antworten » |
| Antoshka | Reguläre Grammatiken 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, 21:01 | Auf diesen Beitrag antworten » |
| eulerscheZahl | 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). |
| 13.02.2016, 23:46 | Auf diesen Beitrag antworten » |
| Antoshka | 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? |
| 14.02.2016, 06:53 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Ja. |
| Anzeige | |
|
|
|
|
|
