Kontextfreie Sprachen: Unterschied zwischen den Versionen

Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 22: Zeile 22:
  
 
<math>G_3 = G_1 \cup G_2 </math> <br/>
 
<math>G_3 = G_1 \cup G_2 </math> <br/>
<math> G_3 = ( V_1 \cup V_2 , T , R_1 \cup R_2 \cup \{S \rightarrow S_1, S_2 \} , S ) </math>
+
<math> G_3 = ( V_1 \cup V_2 \cup \{S\}, T , R_1 \cup R_2 \cup \{S \rightarrow S_1, S_2 \} , S ) </math>
  
  
Zeile 28: Zeile 28:
  
 
<math>G_4 = G_1 \circ G_2</math><br/>
 
<math>G_4 = G_1 \circ G_2</math><br/>
<math>G_4 = ( V_1 \cup V_2 , T , R_1 \cup R_2 \cup \{ S \rightarrow S_1 S_2 \} , S )  </math>
+
<math>G_4 = ( V_1 \cup V_2 \cup \{S\}, T , R_1 \cup R_2 \cup \{ S \rightarrow S_1 S_2 \} , S )  </math>
  
  

Aktuelle Version vom 3. April 2008, 14:56 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>


<math>G_1 =\ ( V_1 , T , R_1 , S_1) </math>
<math>G_2 =\ ( V_2 , T , R_2 , S_2) </math>

Vereinigung

<math>G_3 = G_1 \cup G_2 </math>
<math> G_3 = ( V_1 \cup V_2 \cup \{S\}, T , R_1 \cup R_2 \cup \{S \rightarrow S_1, S_2 \} , S ) </math>


Verknüpfung

<math>G_4 = G_1 \circ G_2</math>
<math>G_4 = ( V_1 \cup V_2 \cup \{S\}, T , R_1 \cup R_2 \cup \{ S \rightarrow S_1 S_2 \} , S ) </math>


Kleensche Hülle

<math>G^* = ( V_1 \cup \{S\} , T , R \cup \{S \rightarrow S_1S \mid \epsilon \ \} , S ) </math>