IP Adressen

2023InformatikEAAufg2D_IP-Adressen.pdf

b)

Grammatik

$$\begin{array}{rl}T& =\{0,1,2,3,4,5,6,7,8,9,.\}\\ NT& =\{S,A,C,E,E\}\\ Startzeichen& =S\end{array}$$

Produktionsregeln

$$\begin{array}{rl}S& \to A.A.A.A\\ A& \to 0DD|1DD|2C\\ C& \to 0D|1D|2D|3D|4D|5E\\ D& \to 0|1|2|3|4|5|6|7|8|9\\ E& \to 0|1|2|3|4|5\end{array}$$

$S\to A.A.A.A\to 1BB.0BB.2C.0BB\to \mathrm{150.000.25}E.057\to \mathrm{150.000.254.057}$

Eingabe	1	4	2	.	2	4	1	.	2	5	0	.	0	5	2
Zustand	$S_0$	$S_1$	$S_2$	$S_3$	$S_4$	$S_9$	$S_7$	$S_8$	$S_0$	$S_4$
Kellerspeicher	#	A 1 #	A 4 1 #	A 2 4 1 #	2 4 1 #	4 1 #	1 #	#	A 2 #	A 0 5 2 #

Besonderheit des Automaten:

• 1 & 2 und 3 & 4 Packet sind Spiegelbilder

Könnte man das Problem mit einem DEA Lösen?

• könnte man, weil man die Länge der Eingabe kennt. Der Automat würde allerdings enorm groß werden