|
|
L(G) = { anbncn : n c N+}
G = {{S,B,C}, {a,b,c},
{ S -> aSBC,
S -> aBC,
CB -> BC,
aB -> ab,
bB -> bb,
bC -> bc,
cC -> cc }, {S} }
Aufgabe 6
a :
fuer L(G) = { a3bn: n c N}
G = {{S,A},{a,b},
{S -> aA,
A -> aB,
B -> aC,
C -> bC,
C -> e }, {S} }
Beweis:
1.
Sei w ein Wort der Sprache L.
zu zeigen: w kann mit Hilfe dieser Grammatik gebildet werden
Hat w die Form a3b0, so kann dieses Wort in 4 Schritten vom Startsymbol abgeleitet werden(S -> aA -> aaB -> aaaC -> aaa).
Hat w die Form a3bn, so kann es in 4 + n Schritten von G abgeleitet werden (S -> aA -> aaB -> aaaC -> aaabC ..... -> aaab...bC -> aaab...b).
2.
Sei w ein aus dieser Grammatik gerbildetes Wort
zu zeigen : w hat die Form a3bn
Ist w in k Schritten von G abgeleitet, so muss k >= 4 sein, da dies die kuerzeste Moeglichkeit ist, ein von dieser Grammatik akzeptiertes Wort zu bilden. Hat w die Laenge 3, so hat es die Form aaa und entspricht damit o.g. Sprache. Hat w die Laenge n > 3, so ist im 5. Schritt der Ableitung C nach bC abgeleitet worden. Da jede Weitere Ableitung die Anzahl der b's im Wort erhoeht oder das Ende der moeglichen Ableitungen darstellt, hat das Wort die Form a3bn.
b :
fuer L(G) = {an mod 2 bn: n c N}
G = {{S,B,C},{a,b},
{S -> aA,
S -> bA,
S -> e,
A -> bB,
B -> bA,
A -> b },{S}}
DFA dazu siehe hinten
Beweis:
1.
Sei w ein Wort der Form an mod 2 bn
zu zeigen: w kann mit Hilfe dieser Grammatik gebildet werden
I.
Sei n=0, dann ist w = e .
Dann kann dieses Wort in einem Schritt vom Startsymbol abgeleitet werden(siehe 3.Regel).
II.
Sei n mod 2 = 0
Worte der Form bn mit n mod 2 = 0 koennen aus dieser Grammatik gebildet werden, indem das Startsymbol nach bA abgeleitet wird. Da von diesem Schritt aus 2k+1 (k c N) Schritte notwendig sind, um die Ableitung zu beenden und damit eine ungerade Anzahl weiterer b's an das vorhandene "angehaengt" werden, sind diese Worte mit der Grammatik bildbar.
II.
Sei n mod 2 = 1
Fuer die Bildung dieser Worte wird im ersten Schritt nach aA abgeleitet.
Von da ist es (wie oben) nur moeglich eine ungerade Anzahl b's "anzuhaengen". Somit koennen auch diese Worte mit der Grammatik erzeugt werden.
2.
Sei w von der Grammatik erzeugt
zu zeigen : w entspricht der Form an mod 2 bn.
Im grunde analog wie oben, das leere Wort ist ableotbar und ist Element der genannten Sprache.
Ist im ersten Schritt nach aA abgeleitet worden, kann nur eine ungerade Anzahl b's erzeugt werden und somit sind die so erzeugten Worte Elemente der Sprache. Ist nach bA abgeleitet worden, gilt das gleiche und da die Summe von 1 und einer ungeraden Zahl immer eine gerade Zahl ist und fuer jede gerade ganze Zahl gilt: z mod 2 = 0 , sind auch die so erzeugten Worte Elemente dieser Sprache. Andere Worte koennen nicht erzeugt werden.
Aufgabe 7
a :
Sei w ein beliebiges Wort, das von diesem Automaten akzeptiert wurde.
W hat die Endsequenz 11, da bei allen anderen moeglichen Endsequenzen der akzeptierende Zustand nicht erreicht werden kann, egal in welchen Zustand der Automat durch lesen von x gelangt ist.
Es werden nur Worte akzeptiert, die mit der Sequenz 11 enden, egal in welchen Zustand der Automat durch lesen von x gelangt ist.
b :
Es werden nur Worte der Form x000y (wobei x und y beliebige 01-Folgen oder das leere Wort sein koennen) akzeptiert, da nur durch ein auftreten solch einer 000 - Sequenz in den akzeptierenden Zustand q3 uebergegangen werden kann. Ist diese Sequenz nicht vorhanden, verbleibt der Automat in einem der nicht akzeptierenden Zustaende.
c :
Da der Automat bei einer Sequenz von 5 aufeinanderfolgenden Einsen in den nicht akzeptierenden Zustand q5 uebergeht, werden alle Worte, in denen diese Sequenz auftritt, nicht akzeptiert. Tritt eine solche Sequenz nicht auf, bleibt der Automat bei beliebiger Zeichenfolge in den Zustaenden q0-q4 und das Wort wird akzeptiert.
Aufgabe 8
a:
alle durch 3 teilbaren binaeren Zahlen akzeptieren ....
???????????????????? Psend kept free because of these great sponsors.a..
|
Other Sponsors electrical connectors, Mangosteen Juice, real estate short sale, Jupiter FL real estate, |
Furniture Markdown Great Deals on furniture - Free Shipping! |
Y-Net Wireless Internet Denver area high speed wireless privider. |
|
|
Dog House Technologies Doghouse Techonologies is located in Tampa Bay FL and offer professional web design, ecommerce development and custom application design for the internet. |
|||