Byte-Welt Wiki - Benutzerbeiträge [de]

LBA (Linear beschränkter Automat)

2008-04-10T11:37:40Z

SeannWilliamScott: Die Seite wurde neu angelegt: Kategorie:Automaten_und_formale_Sprachen Ein LBA (linear beschränkter automaton) akzeptiert Worte einer kontextsensitiven Sprache.

[[Kategorie:Automaten_und_formale_Sprachen]]

Ein LBA (linear beschränkter automaton) akzeptiert Worte einer kontextsensitiven Sprache.

NFA (nichtdeterministischer endlicher Automat)

2008-04-02T16:36:54Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>N\ = ( Z , \Sigma, \delta, Q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow P(Z) </math> 

<math> Q_0 \in Z\ </math> Menge der Startzustände 

<math> E\ \in Z\ </math> Menge der Endzustände 

Akzeptierte Sprache 

<math> L(M) = \{ x_1 , ... , x_n \in \Sigma^* \vert \exists q_0 \in Q_0 , q_1 , ... , q_{n-1} \in Z\ , q_n \in E : q_{i+1} \in \delta ( q_i, x_{i+1} ) \ , \ i = 1, ... , n-1 \} </math>

NFA (nichtdeterministischer endlicher Automat)

2008-04-02T16:32:18Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>N\ = ( Z , \Sigma, \delta, Q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow P(Z) </math> 

<math> Q_0 \in Z\ </math> Menge der Startzustände 

<math> E\ \in Z\ </math> Menge der Endzustände 

Akzeptierte Sprache 

<math> L(M) = \{ x_1 , ... , x_n \in \Sigma \vert \exists q_1 , ... , q_{n-1} \in Z\ , \exists q_0 \in Q_0 , q_n \in E : q_{i+1} \in \delta ( q_i, x_i+1 ) , i = 1, ... , n-1 \in N\ \} </math>

NFA (nichtdeterministischer endlicher Automat)

2008-04-02T16:31:50Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>N\ = ( Z , \Sigma, \delta, Q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow P(Z) </math> 

<math> Q_0 \in Z\ </math> Menge der Startzustände 

<math> E\ \in Z\ </math> Menge der Endzustände 

Akzeptierte Sprache 

<math> L(M) = \{ x_1 , ... , x_n \in \Sigma \vert \exists q_1 , ... , q_{n-1} \in Z\ , \exists q_0 \in Q_0 , q_n \in E : q_{i+1} \in \beta( q_i, x_i+1 ) , i = 1, ... , n-1 \in N\ \} </math>

NFA (nichtdeterministischer endlicher Automat)

2008-04-02T16:22:38Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>N\ = ( Z , \Sigma, \delta, Q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow P(Z) </math> 

<math> Q_0 \in Z\ </math> Menge der Startzustände 

<math> E\ \in Z\ </math> Menge der Endzustände 

Akzeptierte Sprache 

<math> L(M) = { x_1 , ... , x_n \in \Sigma \vert q_1 : q_{i+1} \in \beta( q_i, x_i+1 ) , i = 1, ... , n-1 \in N\ }</math>

DFA (deterministischer endlicher Automat)

2008-04-02T11:16:03Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

Ein deterministischer endlicher Automat , kurz : DFA (deterministic finite automaton), ist nichts anderes als eine abgespekte Turingmaschine, mit deren Hilfe sich eine reguläre Grammatik erzeugen läßt. Was bedeutet, es läßt sich auch überprüfen, ob ein Wort einer bestimmten regulären Sprache angehört. Ein DFA ist auch ein NFA.

Definition: 

<math>M\ = ( Z , \Sigma, \delta, q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow Z </math> 

<math> q_0 \in Z\ </math> Startzustand 

<math> E\ \in Z\ </math> Menge der Endzustände 

Akzeptierte Sprache

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

In einem DFA gibt es einen Startzustand und eine nicht leere Menge von Endzuständen. Es ist genau festgelegt, mit welchen Element des Eingabealphabets zu welchem Zustand gelangt. Das heißt, dass man niemals mit einem Element des Eingabealphabets von einem Zustand zu zwei unterschiedlichen Zustanden gelangen kann.

Mehrfachübergang: 

<math> \delta^*\ (q,\varepsilon) = q\ </math> 
<math> \delta^*\ (q, xa) = \delta ( \delta^*(q,x),a) </math>

Java APIs

2008-04-01T20:38:58Z

SeannWilliamScott:

[[Kategorie:Java]]

==Databanken==

Hibernate -

Maven -

==Loggen==

log4j -

=='''Ich bitte Um Mitarbeit'''==

Kontextsensitive Sprachen

2008-03-30T17:59:17Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math> a^m b^m c^m\ , m = 0 , ... , n \in N </math>
 

Abgeschlossen bzgl:
<ul>
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Kontextsensitive Sprachen

2008-03-30T17:57:58Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math> a^m b^m c^m\ , m = 0 , ... , n \in N </math>

Kontextsensitive Sprachen

2008-03-30T17:51:52Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>a^mb^mc^m\ für m = 0 , ... , n \in \setN </math>

Kontextfreie Sprachen

2008-03-30T17:42:17Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

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 , 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 , 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>

Kontextfreie Sprachen

2008-03-30T17:41:50Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

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 , 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 , 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>

Kontextfreie Sprachen

2008-03-30T17:41:08Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

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 , 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 , 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>

Kontextfreie Sprachen

2008-03-30T17:16:05Z

SeannWilliamScott:

Reguläre Sprachen

2008-03-30T16:47:23Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

Seien <math> T\ , A\ </math> Nichtterminale
und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften: 

<math> T \rightarrow aA </math> Rechtsrekursion, 
<math> T \rightarrow Aa </math> Linksrekursion, 
<math> A \rightarrow a </math>

Überführungsfunktion für einen DFA: 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

Abgeschlossen bzgl:
<ul>
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Komplement

Bei einem Automat, der das Komplement akzeptiert, werden alle Nicht-Endzustände zu Endzuständen und umgekehrt.

<math> M = ( Z\ , \Sigma , \delta, q_0 , Z\ \backslash E\ ) </math> 

Schnitt 

<math>M = ( Z\ , \Sigma , \delta , p_0 , E\ ) </math> 
<math>N = ( Z\ , \Sigma , \delta , q_0 , E\ ) </math> 
<math> M\ \bigcap N\ = ( \Z_M \times \Z_N , \Sigma , \delta^* , (p_0, q_0) , E_M\ \times E_N\ ) </math> 

<math> \delta^*( ( p,q ), a ) = ( \delta_M (p,a), \delta_N (q,a) )\ </math>

Vereinigung 

<math> M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } } </math> ( de Morgansche Regel ) 

Verknüpfung 

<math> M \circ N = ( Z_1 \cup Z_2 , \Sigma , \delta , Q_1 , E ) </math>

<math> \delta ( p , a ) = \begin{cases} \delta_M( p ,a ) , p \in Z_1 \backslash E_1 \\ \delta_M ( p , a ) \cup \bigcup_{q \in Q_2} \delta_N ( q , a ) , p \in E_1 \\ \delta_N ( p , a ) , sonst \end{cases} </math>

<math> E\ = \begin{cases} E_1 \bigcup E_2 , Q_2 \bigcap E_2 \neq \emptyset \\ E_2 , sonst \end{cases} </math> 

Kleensche Hülle 

<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math> 
<math> \delta^*( p , a ) = \begin{cases} \delta(p , a) \cup \bigcup_{q \in Q} \delta(q, a) , p \in E_1 \\ \delta( p , a ) , sonst \end{cases} </math>

Reguläre Sprachen

2008-03-30T16:46:41Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

Seien <math> T\ , A\ </math> Nichtterminale
und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften: 

<math> T \rightarrow aA </math> Rechtsrekursion, 
<math> T \rightarrow Aa </math> Linksrekursion, 
<math> A \rightarrow a </math>

Überführungsfunktion für einen DFA: 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

Abgeschlossen bzgl:
<ul>
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Komplement

Bei einem Automat, der das Komplement akzeptiert, werden alle Nicht-Endzustände zu Endzuständen und umgekehrt.

<math> M = ( Z\ , \Sigma , \delta, q_0 , Z\ \backslash E\ ) </math> 

Schnitt 

<math>M = ( Z\ , \Sigma , \delta , p_0 , E\ ) </math> 
<math>N = ( Z\ , \Sigma , \delta , q_0 , E\ ) </math> 
<math> M\ \bigcap N\ = ( \Z_M \times \Z_N , \Sigma , \delta^* , (p_0, q_0) , E_M\ \times E_N\ ) </math> 

<math> \delta^*( ( p,q ), a ) = ( \delta_M (p,a), \delta_N (q,a) )\ </math>

Vereinigung 

<math> M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } } </math> ( de Morgansche Regel ) 

Verknüpfung 

<math> M \circ N = ( Z_1 \cup Z_2 , \Sigma , \delta , Q_1 , E ) </math>

<math> \delta ( p , a ) = \begin{cases} \delta_M( p ,a ) , p \in Z_1 \backslash E_1 \\ \delta_M ( p , a ) \cup \bigcup_{q \in Q_2} \delta_N ( q , a ) , p \in E_1 \\ \delta_N ( p , a ) , sonst \end{cases} </math>

<math> E\ = \begin{cases} E_1 \bigcup E_2 , Q_2 \bigcap E_2 \neq \emptyset \\ E_2 , sonst \end{cases} </math> 

Kleensche Hülle 

<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math> 
<math> \delta^*( p , a ) = \begin{cases} \delta(p , a) \cup \bigcup_{q \in Q} \delta(q, a) , p \in E \\ \delta( p , a ) , sonst \end{cases} </math>

Reguläre Sprachen

2008-03-30T16:23:44Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

Seien <math> T\ , A\ </math> Nichtterminale
und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften: 

<math> T \rightarrow aA </math> Rechtsrekursion, 
<math> T \rightarrow Aa </math> Linksrekursion, 
<math> A \rightarrow a </math>

Überführungsfunktion für einen DFA: 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

Abgeschlossen bzgl:
<ul>
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Komplement

Bei einem Automat, der das Komplement akzeptiert, werden alle Nicht-Endzustände zu Endzuständen und umgekehrt.

<math> M = ( Z\ , \Sigma , \delta, q_0 , Z\ \backslash E\ ) </math> 

Schnitt 

<math>M = ( Z\ , \Sigma , \delta , p_0 , E\ ) </math> 
<math>N = ( Z\ , \Sigma , \delta , q_0 , E\ ) </math> 
<math> M\ \bigcap N\ = ( \Z_M \times \Z_N , \Sigma , \delta^* , (p_0, q_0) , E_M\ \times E_N\ ) </math> 

<math> \delta^*( ( p,q ), a ) = ( \delta_M (p,a), \delta_N (q,a) )\ </math>

Vereinigung 

<math> M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } } </math> ( de Morgansche Regel ) 

Verknüpfung 

<math> \begin{cases} \delta_M( p ,a ) , p \in Z_1 \backslash E_1 \\ \delta_M ( p , a ) \cup \bigcup_{q \in Q_2} \delta_N ( q , a ) , p \in E_1 \\ \delta_N ( q , a ) , sonst \end{cases} </math>

<math> E\ = \begin{cases} E_1 \bigcup E_2 , Q_2 \bigcap E_2 \neq \emptyset \\ E_2 , sonst \end{cases} </math>

Reguläre Sprachen

2008-03-30T15:37:18Z

SeannWilliamScott:

Kontextfreie Sprachen

2008-03-25T13:27:36Z

SeannWilliamScott:

Kontextfreie Sprachen

2008-03-25T13:25:04Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

Eine kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden Kellerauotmaten 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>

Kontextfreie Sprachen

2008-03-25T13:22:57Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

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>

Kontextfreie Sprachen

2008-03-25T13:22:06Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

Sei <math> T\ , A_i </math> ein Nichtterminal
und <math> a_i </math> ein Terminal, für i = 0 , ... , n .

<math> T\ \rightarrow \{A_i \vert a_i \}^* </math> und
<math> T\ \rightarrow \varepsilon</math>

Reguläre Sprachen

2008-03-25T12:47:47Z

SeannWilliamScott:

Reguläre Sprachen

2008-03-25T12:45:50Z

SeannWilliamScott:

Reguläre Sprachen

2008-03-25T12:43:13Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<math> T \rightarrow aT </math> Rechtsrekursion, 
<math> T \rightarrow Ta </math> Linksrekursion, 
<math> T \rightarrow a </math>

Überführungsfunktion für einen DFA: 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

Abgeschlossen bzgl:
<ul>
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Kontextsensitive Sprachen

2008-03-25T04:32:52Z

SeannWilliamScott: Die Seite wurde neu angelegt: Kategorie:Automaten und formale Sprachen

[[Kategorie:Automaten und formale Sprachen]]

Kontextfreie Sprachen

2008-03-25T04:31:27Z

SeannWilliamScott: Die Seite wurde neu angelegt: Kategorie:Automaten und formale Sprachen

[[Kategorie:Automaten und formale Sprachen]]

DFA (deterministischer endlicher Automat)

2008-03-25T04:22:32Z

SeannWilliamScott:

DFA (deterministischer endlicher Automat)

2008-03-25T04:20:41Z

SeannWilliamScott:

DFA (deterministischer endlicher Automat)

2008-03-25T04:12:58Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>M\ = ( Z , \Sigma, \delta, q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow Z </math> 

<math> q_0 \in Z\ </math> Startzustand 

<math> E\ \in Z\ </math> Menge der Endzustände 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

NFA (nichtdeterministischer endlicher Automat)

2008-03-25T04:12:34Z

SeannWilliamScott:

NFA (nichtdeterministischer endlicher Automat)

2008-03-25T04:07:00Z

SeannWilliamScott:

DFA (deterministischer endlicher Automat)

2008-03-25T04:06:38Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>M\ = ( Z , \Sigma, \delta, q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow Z </math> 

<math> q_0 \in Z\ </math> Startzustand 

<math> E\ </math> Menge der Endzustände 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

DFA (deterministischer endlicher Automat)

2008-03-25T04:05:01Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>L(M)\ = ( Z , \Sigma, \delta, q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow Z </math> 

<math> q_0 \in Z\ </math> Startzustand 

<math> E\ </math> Menge der Endzustände 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

NFA (nichtdeterministischer endlicher Automat)

2008-03-25T04:04:30Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>L(M)\ = ( Z , \Sigma, \delta, Q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow P(Z) </math> 

<math> Q_0 \in Z\ </math> Menge der Startzustände 

<math> E\ </math> Menge der Endzustände

DFA (deterministischer endlicher Automat)

2008-03-25T04:03:25Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>L(M)\ = ( Z , \Sigma, \delta, q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow Z </math> 

<math> Q_0 \in Z\ </math> Startzustand 

<math> E\ </math> Menge der Endzustände 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

DFA (deterministischer endlicher Automat)

2008-03-25T04:02:46Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>L(M)\ = ( Z , \Sigma, \delta, Q_0, E )</math>
 

<math> Z\ </math> Menge der Zustände 

<math> \Sigma\ </math> Menge des Eingabealphabets 

<math> \delta\ : Z \times \Sigma \rightarrow Z </math> 

<math> Q_0 \in Z\ </math> Startzustand 

<math> E\ </math> Menge der Endzustände 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

DFA (deterministischer endlicher Automat)

2008-03-25T03:52:04Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

NFA (nichtdeterministischer endlicher Automat)

2008-03-25T03:50:48Z

SeannWilliamScott: Die Seite wurde neu angelegt: Kategorie:Automaten und formale Sprachen

[[Kategorie:Automaten und formale Sprachen]]

DFA (deterministischer endlicher Automat)

2008-03-25T03:48:53Z

SeannWilliamScott: Die Seite wurde neu angelegt: Kategorie:Automaten und formale Sprachen

[[Kategorie:Automaten und formale Sprachen]]

Reguläre Sprachen

2008-03-25T03:44:23Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

Überführungsfunktion für einen DFA: 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

Abgeschlossen bzgl:
<ul>
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Reguläre Sprachen

2008-03-25T03:43:06Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

Überführungsfunktion für einen DFA: 

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

<ul>
Abgeschlossen bzgl:
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Reguläre Sprachen

2008-03-25T03:39:00Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{i+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

<ul>
Abgeschlossen bzgl:
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Reguläre Sprachen

2008-03-25T03:38:37Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<math>L(M) = \{ x_1 ... x_n \in {\Sigma^*} \vert \exists q_1 ... q_{n-1} \in Z , q_n \in E\ : \delta (q_i,x_{i+1}) = q_{n+1} </math> für<math>\ i = 0, ... , n-1 \} </math>

<ul>
Abgeschlossen bzgl:
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Reguläre Sprachen

2008-03-25T03:18:48Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<ul>
Abgeschlossen bzgl:
<li><math> \cup\ </math> Vereinigung</li>
<li><math> \cap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Reguläre Sprachen

2008-03-25T03:15:13Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<ul>
Abgeschlossen bzgl:
<li><math> \bigcup\ </math> Vereinigung</li>
<li><math> \bigcap\ </math> Schnitt</li>
<li><math> ^- </math> Komplement</li>
<li><math> \circ\ </math> Verknüpfung</li>
<li><math> *\ </math> Sternhülle</li>
</ul>

Reguläre Sprachen

2008-03-25T03:12:06Z

SeannWilliamScott:

[[Kategorie:Automaten und formale Sprachen]]

='''Reguläre Sprache'''=

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<ul>
Abgeschlossen bzgl:
<li><math> \bigcup\ </math> Vereinigung</li>
<li><math> \bigcap\ </math>Schnitt</li>
<li><math> ^- </math>Komplement</li>
<li><math> \circ\ </math>Verknüpfung</li>
<li><math> *\ </math>Sternhülle</li>
</ul>

Grammatiken

2008-03-24T21:29:42Z

SeannWilliamScott:

[[Kategorie:Theoretische_Informatik]]

<math> G\ = ( V\ , \Sigma , P\ , S\ ) </math>

<math>V\ </math> endliche Menge der Variablen, nicht terminal Symbole 
<math>\Sigma\ </math> endliche Menge von terminal Symbolen, Alphabet 
<math>P\ </math> Regeln 
<math>S\ </math> Startsymbol , <math>S\ </math> 

Je nach Spracheklasse unterliegen Grammtikregeln einer gewissen Form.

<math> REG \subset DCFL \subset CFL \subset DCSL \subseteq CSL \subset REC \subset RE </math>

<math> REG\ </math> Menge der regulären Sprachen 
<math> DCFL\ </math> Menge der deterministisch kontextfreien Sprachen 
<math> CFL\ </math> Menge der kontextfreien Sprachen 
<math> DCSL\ </math> Menge der deterministisch kontext-sensitiv Sprachen 
<math> CSL\ </math> Menge der kontext-sensitiv Sprachen 
<math> REC\ \ </math> Menge der rekursive aufzählbaren Sprachen 
<math> RE\ \ </math> Menge der Sprachen

Grammatiken

2008-03-24T21:22:09Z

SeannWilliamScott:

[[Kategorie:Theoretische_Informatik]]

<math> G\ = ( V\ , \Sigma , P\ , S\ ) </math>

<math>V\ </math> endliche Menge der Variablen, nicht terminal Symbole 
<math>\Sigma\ </math> endliche Menge von terminal Symbolen, Alphabet 
<math>P\ </math> Regeln 
<math>S\ </math> Startsymbol , <math>S\ </math> 

Je nach Spracheklasse unterliegen Grammtikregeln einer gewissen Form.

<math> REG \subset DCFL \subset CFL \subset DCSL \subseteq CSL \subset REC \subset RE </math>

<math> REG\ </math> Menge der regulären Sprachen 
<math> DCFL\ </math> Menge der deterministisch kontextfreien Sprachen 
<math> CFL\ </math> Menge der kontextfreien Sprachen 
<math> CSL\ </math> Menge der kontext-sensitiv Sprachen 
<math> RE\ \ </math> Menge der rekursive aufzählbaren Sprachen

Grammatiken

2008-03-24T21:17:35Z

SeannWilliamScott:

[[Kategorie:Theoretische_Informatik]]

<math> G\ = ( V\ , \Sigma , P\ , S\ ) </math>

<math>V\ </math> endliche Menge der Variablen, nicht terminal Symbole 
<math>\Sigma\ </math> endliche Menge von terminal Symbolen, Alphabet 
<math>P\ </math> Regeln 
<math>S\ </math> Startsymbol , <math>S\ </math> 

Je nach Spracheklasse unterliegen Grammtikregeln einer gewissen Form.

<math> REG \subset DCFL \subseteq CFL \subseteq CSL \subseteq RE </math>

<math> REG\ </math> Menge der regulären Sprachen 
<math> DCFL\ </math> Menge der deterministisch kontextfreien Sprachen 
<math> CFL\ </math> Menge der kontextfreien Sprachen 
<math> CSL\ </math> Menge der kontext-sensitiv Sprachen 
<math> RE\ \ </math> Menge der rekursive aufzählbaren Sprachen