Unikram zum Wochenende

Zum Wochenende noch zwei Auszüge aus den heutigen Übungen:

erstmal der Logik Haiku aus TGI welcher in seiner Schönheit eigentlich kaum zu überbieten ist.
Aufg. : Zeigen sie, anhand der charakteristischen Gleichungen, das man ein D-Flip-Flop erhält wenn man die Eingänge eines JK-Flip-Flops folgendermaßen verschaltet: J=D K=D'
Da JK: Q+= JQ'+K'Q und T: Q+=TQ'+T'Q ergibt sich:

sei J=D
sei K=D'
damit sei K'=D

und da DQ'+DQ=Q+ <=> D=Q+
q.e.d.
------------------------------------------------------------------------

Der Beweis aus FGI hat mir gefallen da ich selber drauf gekommen bin:

G=((X),(1,0),P,X) P: X-> ε|0|1|0X0|1X1

Beweisen sie das L(G) = PALINDROM
(zu deutsch: Beweisen sie das mit dieser Grammatik Palindrome erzeugt werden)

Es ergeben sich zwei Richtungen:
I. kann ich mit der Grammatik alle(!) Palindrome(!) aus E erzeugen?
II. erzeugt die Grammatik nur Palindrome?

I:
Ein PALINDROM hat die Form uvu²
wobei u² = (rückwärts) u, ui = u²i
und v element E|ε
bsp:
uvu² = 001000100

Betrachtung der Transitionsreglen:

• v wird von X->ε|0|1 beinflußt: das Alphabet E und ε werden berücksichtigt und die Form uvu² wird nicht beeinflußt
• u,u² werden von X->0X0|1X1 beinflußt: wieder wird gesamt E (ohne ε) berücksichtigt und die Form beibehalten!

=> G erzeugt alle Palindrome aus E

II:
besagte Form uvu² gilt weiterhin
Ein Wort der Länge 1 besteht entweder aus ε oder einem Buchstaben des Alphabets = Palindrom u,u² = ε v= ε|0|1. Um eine weitere Transition und damit die Wortlänge zu erhöhen haben wir X-> 0X0|1X1 zur Verfügung! Da 1 und 0 E darstellen kann man die Regel auf eXe (e=ein Buchstabe aus E) abstrahieren. Hierbei ist logischerweise sichergestellt das das gesamte E benutzt werden kann. Die Regel X->eXe verändert die Form uvu² nur insofern das sie ein u,u² anhängt welches den gleichen Inhalt hat, was keinen Verstoß darstellt.

=> G erzeugt nur Palindrome

aus I und II folgt daher:
L(G) = PALINDROM
q.e.d.