Reguläre Sprachen - Versionsgeschichte

SeannWilliamScott am 30. März 2008 um 16:47 Uhr

2008-03-30T16:47:23Z

← Nächstältere Version		Version vom 30. März 2008, 16:47 Uhr
Zeile 58:		Zeile 58:

	<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math><br/>		<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math><br/>
	<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> <br/>		<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> <br/>

2008-03-30T16:46:41Z

← Nächstältere Version		Version vom 30. März 2008, 16:46 Uhr
Zeile 49:		Zeile 49:
	<b>Verknüpfung</b> <br/>		<b>Verknüpfung</b> <br/>

	<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> M \circ N = ( Z_1 \cup Z_2 , \Sigma , \delta , Q_1 , E ) </math>

	<math> E\ = \begin{cases} E_1 \bigcup E_2 , Q_2 \bigcap E_2 \neq \emptyset \\ E_2 , sonst \end{cases} </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> <br/>

			<b>Kleensche Hülle </b>

			<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math><br/>
			<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> <br/>

2008-03-30T16:23:44Z

← Nächstältere Version		Version vom 30. März 2008, 16:23 Uhr
Zeile 44:		Zeile 44:
	<b>Vereinigung</b> <br/>		<b>Vereinigung</b> <br/>

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


			<b>Verknüpfung</b> <br/>

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







	<b>~~Verknüpfung~~</b>

2008-03-30T15:37:18Z

← Nächstältere Version		Version vom 30. März 2008, 15:37 Uhr
Zeile 25:		Zeile 25:
	<li><math> *\ </math> Sternhülle</li>		<li><math> *\ </math> Sternhülle</li>
	</ul>		</ul>

			<b>Komplement</b>

			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> <br/>



			<b>Schnitt</b> <br/>

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

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

			<b>Vereinigung</b> <br/>

			<math> M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } } </math>












			<b>Verknüpfung</b>

2008-03-25T12:47:47Z

← Nächstältere Version		Version vom 25. März 2008, 12:47 Uhr
Zeile 5:		Zeile 5:
	Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.		Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

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

2008-03-25T12:45:50Z

← Nächstältere Version		Version vom 25. März 2008, 12:45 Uhr
Zeile 5:		Zeile 5:
	Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.		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, <br/>		Sei <math> T\ , A\ </math> sind Nichtterminale <br/>
	<math> T \rightarrow Ta </math> Linksrekursion, <br/>		und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften:<br/>
	<math> T \rightarrow a </math>
			<math> T \rightarrow aA </math> Rechtsrekursion, <br/>
			<math> T \rightarrow Aa </math> Linksrekursion, <br/>
			<math> A \rightarrow a </math>

	Überführungsfunktion für einen DFA: <br/>		Überführungsfunktion für einen DFA: <br/>

2008-03-25T12:43:13Z

← Nächstältere Version		Version vom 25. März 2008, 12:43 Uhr
Zeile 5:		Zeile 5:
	Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.		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, <br/>
			<math> T \rightarrow Ta </math> Linksrekursion, <br/>
			<math> T \rightarrow a </math>

	Überführungsfunktion für einen DFA: <br/>		Überführungsfunktion für einen DFA: <br/>

2008-03-25T03:44:23Z

← Nächstältere Version		Version vom 25. März 2008, 03:44 Uhr
Zeile 11:		Zeile 11:


			<b>Abgeschlossen bzgl:</b>
	<ul>		<ul>
	~~Abgeschlossen bzgl:~~
	<li><math> \cup\ </math> Vereinigung</li>		<li><math> \cup\ </math> Vereinigung</li>
	<li><math> \cap\ </math> Schnitt</li>		<li><math> \cap\ </math> Schnitt</li>

2008-03-25T03:43:06Z

← Nächstältere Version		Version vom 25. März 2008, 03:43 Uhr
Zeile 5:		Zeile 5:
	Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.		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: <br/>

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

2008-03-25T03:39:00Z

← Nächstältere Version		Version vom 25. März 2008, 03:39 Uhr
Zeile 6:		Zeile 6:


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