Kontextfreie Sprachen: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| (8 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| 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 | ||
| Zeile 8: | Zeile 9: | ||
<math> T\ \rightarrow \{A_i \vert a_i \}^* </math> und | <math> T\ \rightarrow \{A_i \vert a_i \}^* </math> und | ||
<math> T\ \rightarrow \varepsilon</math> | <math> T\ \rightarrow \varepsilon</math> | ||
<b>Beispielsprache:</b> <br/> | |||
<math>a^mb^m\ </math> | |||
<br/> | |||
<math>G_1 =\ ( V_1 , T , R_1 , S_1) </math> <br/> | |||
<math>G_2 =\ ( V_2 , T , R_2 , S_2) </math> | |||
<b>Vereinigung</b> | |||
<math>G_3 = G_1 \cup G_2 </math> <br/> | |||
<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> | |||
<b>Verknüpfung</b> | |||
<math>G_4 = G_1 \circ G_2</math><br/> | |||
<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> | |||
<b>Kleensche Hülle</b> | |||
<math>G^* = ( V_1 \cup \{S\} , T , R \cup \{S \rightarrow S_1S \mid \epsilon \ \} , S ) </math> <br/> | |||
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 $ T\ ,A_{i} $ ein Nichtterminal und $ a_{i} $ ein Terminal, für i = 0 , ... , n , so gelten folgende Bildungsvorschriften:
$ T\ \rightarrow \{A_{i}\vert a_{i}\}^{*} $ und $ T\ \rightarrow \varepsilon $
Beispielsprache:
$ a^{m}b^{m}\ $
$ G_{1}=\ (V_{1},T,R_{1},S_{1}) $
$ G_{2}=\ (V_{2},T,R_{2},S_{2}) $
Vereinigung
$ G_{3}=G_{1}\cup G_{2} $
$ 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
$ G_{4}=G_{1}\circ G_{2} $
$ 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
$ G^{*}=(V_{1}\cup \{S\},T,R\cup \{S\rightarrow S_{1}S\mid \epsilon \ \},S) $
