Rechtslineare Grammatik: Difference between revisions
Jump to navigation
Jump to search
WikiLingua (talk | contribs) No edit summary |
Marked as {{ref}} |
||
| (One intermediate revision by one other user not shown) | |||
| Line 2: | Line 2: | ||
Eine [[Grammatik]] G heisst rechtslinear, wenn alle Produktionen die Form '''A''' => '''xB''' haben, wobei '''B''' Element des nicht-terminalen Vokabulars ist und auch leer sein kann, nicht jedoch '''x''', welches Element des terminalen Vokabulars ist. Dann ist die Klasse der Sprachen, die durch rechtslineare Grammatiken erzeugt werden dieselbe, die auch durch [[linkslineare Grammatik|linkslineare Grammatiken]] erzeugt werden, nämlich die Klasse der [[reguläre Sprachen|regulären Sprachen]]. | Eine [[Grammatik]] G heisst rechtslinear, wenn alle Produktionen die Form '''A''' => '''xB''' haben, wobei '''B''' Element des nicht-terminalen Vokabulars ist und auch leer sein kann, nicht jedoch '''x''', welches Element des terminalen Vokabulars ist. Dann ist die Klasse der Sprachen, die durch rechtslineare Grammatiken erzeugt werden dieselbe, die auch durch [[linkslineare Grammatik|linkslineare Grammatiken]] erzeugt werden, nämlich die Klasse der [[reguläre Sprachen|regulären Sprachen]]. | ||
{{wb}} | {{wb}}{{ref}} | ||
[[Category: | [[Category:Computational Linguistics]] | ||
Latest revision as of 17:35, 24 July 2014
Definition
Eine Grammatik G heisst rechtslinear, wenn alle Produktionen die Form A => xB haben, wobei B Element des nicht-terminalen Vokabulars ist und auch leer sein kann, nicht jedoch x, welches Element des terminalen Vokabulars ist. Dann ist die Klasse der Sprachen, die durch rechtslineare Grammatiken erzeugt werden dieselbe, die auch durch linkslineare Grammatiken erzeugt werden, nämlich die Klasse der regulären Sprachen.
| REF | This article has no reference(s) or source(s). Please remove this block only when the problem is solved. |