Übungsklausur Lösung

Informatik 1 - Übungsklausur

Lösung

Übungsklausur

1) Markov-Algorithmus
a)

1.	a\|	->	\|a
2.	a*	->	*b
3.	b\|	->	\|cb
4.	b	->	epsilon
5.	c\|	->	\|c
6.	dc	->	\|d
7.	d	->.	epsilon
8.	\|	->	a
9.	*	->	d
10.	ac	->	c

b) |||*|| -(8)-> a||*|| -(1)-> |a|*|| -(1)-> ||a*|| -(2)-> ||*b||

-(3)-> ||*cb| -(3)-> ||*|c|cb -(4)-> ||*|c|c -(5)-> ||*||cc -(8)-> a|*||cc

-(1)-> |a*||cc -(2)-> |*b||cc -(3)-> |*|cb|cc -(3)-> |*|c|cbcc -(4)-> |*|c|ccc

-(5)-> |*||cccc -(8)-> a*||cccc -(2)-> *b||cccc -(3)-> *|cb|cccc -(3)-> *|c|cbcccc

-(4)-> *|c|ccccc -(5)-> *||cccccc -(8)-> *a|cccccc -(1)-> *|acccccc -(10)-> *|cccccc

-(8)-> *acccccc -(10)-> *cccccc -(9)-> dcccccc -(6)-> |dccccc -(6)-> ||dcccc -(6)-> |||dccc

-(6)-> ||||dcc -(6)-> |||||dc -(6)-> ||||||d -(7)->. ||||||

2) Grammatik
a) Die Grammatik ist CH-3.

b) Die erzeugte Sprache lautet

L = { a* { b c* }* a }

c)

3) Grammatik
G:= ( {S, B, W}, {a,b}, S, P)
P:= { S -> aSW | B, B -> bBW | bW, W -> a | b }

Es gibt keine reguläre Grammatik, die diese Sprache erzeugt.

4) Boolsche Algebra

5) Algebra
a)
Get(Ins(Del(Ins(Ins(create,1),2)),3))   (A2)
= Get(Ins(Ins(Del(Ins(create,1),2)),3))    (A1)
= Get(Ins(Ins(create,2),3))    (A4)
= Get(Ins(create,2))   (A3)
= 2

b) Get(Ins(Ins(Del(Ins(create,3)),4),Get(Ins(Ins(create,5),6))))    (A1,A4)
= Get(Ins(Ins(create,4),Get(Ins(create,5))))    (A3)
= Get(Ins(Ins(create,4),5))     (A4)
= Get(Ins(create,4))     (A3)
= 4

6) Lambda-Kalkül
a)