Formale Grammatik Grundregeln?
Hallo,
ein paar kurze Fragen die ich nicht richtig verstehe:
wie viele terminale und nichtterminale dürfen bei den Formalen übergangsfunktionen auf der rechten Seite vom Pfeil stehen?(links darf immer nur eine nichtterminale stehen?)
reguläre Ausdrücke sind einfach nur eine andere Form von regulären Sprachen? (Wenn nicht, worin unterscheiden sie sich?)
müssen formale Sprachen jedes akzeptierte Wort berücksichtigen oder kann eine sprache auch einfach eine teilmenge aller akzeptierter Wörter sein?
danke für alle hilfreichen Antworten
1 Antwort
wie viele terminale und nichtterminale dürfen bei den Formalen übergangsfunktionen auf der rechten Seite vom Pfeil stehen?
Rechts stehen beliebig viele Terminale und Nichtterminale. Manchmal wird das Startsymbol dabei explizit verboten. Das hat vermutlich nur formale Gründe und stellt keine wirkliche Einschränkung dar.
(links darf immer nur eine nichtterminale stehen?)
Nein: Auch hier dürfen beliebig viele Symbole stehen, allerdings muss mindestens ein Nichtterminal dabei sein. Ich vermute, dass auch dies nur eine Formalität ist.
reguläre Ausdrücke sind einfach nur eine andere Form von regulären Sprachen? (Wenn nicht, worin unterscheiden sie sich?)
In der theoretischen Informatik: Ja. Zu jeder regulären Sprache gibt es einen regulären Ausdruck und umgekehrt.
In der Praxis (z. B. bei der Suchfunktion im Editor) findet man aber oft nützliche Erweiterungen, die darüber hinausgehen: "\(a\)*b\1" findet alle Wörter der Form aⁿbaⁿ, was keine reguläre Sprache schafft.
müssen formale Sprachen jedes akzeptierte Wort berücksichtigen oder kann eine sprache auch einfach eine teilmenge aller akzeptierter Wörter sein?
Eine Sprache wird durch die Menge aller von ihr akzeptierten Wörter definiert. Zwei Sprachen sind genau dann gleich, wenn sie dieselben Wörter erkennen.