Kontextfreie Sprachen: Unterschied zwischen den Versionen

Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen
Zeile 12: Zeile 12:
 
<b>Beispielsprache:</b> <br/>
 
<b>Beispielsprache:</b> <br/>
  
<math>a^mb^mc^m</math>
+
<math>a^mb^m</math>

Version vom 29. März 2008, 20:09 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>

Beispielsprache:

<math>a^mb^m</math>