Kontextfreie Sprachen: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen| Zeile 1: | Zeile 1: | ||
[[Kategorie:Automaten und formale Sprachen]] | [[Kategorie:Automaten und formale Sprachen]] | ||
| − | Eine kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden Kellerauotmaten erzeugen. | + | Eine kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden Kellerauotmaten (PDA) erzeugen. |
| + | Eine deterministisch kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden deterministischen Kellerauotmaten (DPDA) erzeugen. | ||
Seien <math> T\ , A_i </math> ein Nichtterminal | Seien <math> T\ , A_i </math> ein Nichtterminal | ||
Version vom 25. März 2008, 13:27 Uhr
Eine kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden Kellerauotmaten (PDA) erzeugen.
Eine deterministisch kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden deterministischen Kellerauotmaten (DPDA) erzeugen.
Seien <math> T\ , A_i </math> ein Nichtterminal und <math> a_i </math> ein Terminal, für i = 0 , ... , n , so gelten folgende Bildungsvorschriften:
<math> T\ \rightarrow \{A_i \vert a_i \}^* </math> und <math> T\ \rightarrow \varepsilon</math>
