Links und Funktionen
Sprachumschaltung

Navigationspfad


Inhaltsbereich

Lösung 05

Plain Text icon loesung05.txt — Plain Text, 1 KB

Dateiinhalt

Musterloesung Blatt 5
---------------------


H-10:

Sei A = (Q,Sigma,delta,q0,F) ein DEA, der L erkennt.

Sei q' := delta^(q0,w) 

Dann wird w\L erkannt von A' = (Q,Sigma,delta,q',F), denn
es gilt:
v in L(A') 
<=>  delta^(q',v) in F 
<=>  delta^( delta^(q0,w) , v ) in F 
<=>  delta^( q0, wv ) in F 
<=>  wv in L 
<=>  v in w\L 

Sei nun F' := { q in Q ; delta^(q,w) in F }

Dann wird L/w erkannt von A'' = (Q,Sigma,delta,q0,F'), denn
ws gilt:
v in L(A'') 
<=> delta^( q0 , v ) in F'   
<=> delta^( delta^(q0,v) , w ) in F 
<=> delta^( q0 , vw ) in F 
<=> vw in L
<=> v in L/w


H-11

S => ASB => AASBB => AAABBB
  => aAAABBB => acAABBB
  => accABBB
  => accaABBB => accaaABBB => accaacBBB
  => accaaccBB
  => accaaccbBB => accaaccbcB
  => accaaccbcbB => accaaccbcbc

Artikelaktionen


Funktionsleiste