Kontextfreie Sprachen: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| (3 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 12: | Zeile 12: | ||
<b>Beispielsprache:</b> <br/> | <b>Beispielsprache:</b> <br/> | ||
<math>a^mb^m</math> | <math>a^mb^m\ </math> | ||
<br/> | <br/> | ||
<math>G_1 = ( V_1 , T , R_1 , S_1) </math> | <math>G_1 =\ ( V_1 , T , R_1 , S_1) </math> <br/> | ||
<math>G_2 = ( V_2 , T , R_2 , S_2) </math> | <math>G_2 =\ ( V_2 , T , R_2 , S_2) </math> | ||
<b>Vereinigung</b> | <b>Vereinigung</b> | ||
<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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): T\ , A_i ein Nichtterminal und Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): a_i ein Terminal, für i = 0 , ... , n , so gelten folgende Bildungsvorschriften:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): T\ \rightarrow \{A_i \vert a_i \}^* und Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): T\ \rightarrow \varepsilon
Beispielsprache:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): a^mb^m\
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G_1 =\ ( V_1 , T , R_1 , S_1)
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G_2 =\ ( V_2 , T , R_2 , S_2)
Vereinigung
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G_3 = G_1 \cup G_2
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G_3 = ( V_1 \cup V_2 \cup \{S\}, T , R_1 \cup R_2 \cup \{S \rightarrow S_1, S_2 \} , S )
Verknüpfung
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G_4 = G_1 \circ G_2
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G_4 = ( V_1 \cup V_2 \cup \{S\}, T , R_1 \cup R_2 \cup \{ S \rightarrow S_1 S_2 \} , S )
Kleensche Hülle
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): G^* = ( V_1 \cup \{S\} , T , R \cup \{S \rightarrow S_1S \mid \epsilon \ \} , S )
