Difference between revisions of "Rechtslineare Grammatik"

From Glottopedia
Jump to navigation Jump to search
(New page: ==Definition== Eine Grammatik G heisst rechtslinear, wenn alle Produktionen die Form '''A''' <math>\Rightarrow</math> '''xB''' haben, wobei '''B''' auch leer sein kann, nicht jedoch ''...)
 
Line 1: Line 1:
 
==Definition==
 
==Definition==
Eine [[Grammatik]] G heisst rechtslinear, wenn alle Produktionen die Form '''A''' <math>\Rightarrow</math> '''xB''' haben, wobei '''B''' auch leer sein kann, nicht jedoch '''x'''! Dann ist die Klasse der Sprachen, die durch rechtslineare Grammatiken erzeugt werden die selbe, 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}}
 
[[Category:Computerlinguistik]]
 
[[Category:Computerlinguistik]]

Revision as of 11:41, 12 July 2007

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.