THI2 UE02

2.

Für einzel Input:
$X\to w$
$w=w_1,w_2,...,w_n\in N\cup \Sigma \cup \{\epsilon \}$

Mann kann jede Regel als:
$X\to W_1{X}_1$
$X_1\to W_2{X}_2$
…
$X_n\to \epsilon$
dargestellen.
Dabei gilt $W_x\to w_x$

Für mehrfache Eingabe Zeichen:
$w_i\to w_o$
$w_i=w_{i1},w_{i2},...,w_{in}\in N\cup \Sigma \cup \{\epsilon \}$
$w_o=w_{o1},w_{o2},...,w_{on}\in N\cup \Sigma \cup \{\epsilon \}$

XYZ -> ABC
XX_1 ->
X_1Y ->
Y_1Z ->

?????

3.

$L(G)=\{a^n{b}^m{c}^{nm}\}$

$S\to XE$
$X\to aX{C}_n|bY$
$Y{C}_n\to bY{C}_n{C}_{m}Z$
$Z{C}_n\to C_b{C}_{m}Z$
$ZE\to VE$
$C_{m}V\to V{C}_m$
$C_{b}V\to V{C}_n$
$YV\to Y$
$Z{C}_m\to C_{m}Z$
$Y\to F$
$F{C}_n\to cF$
$F{C}_m\to cF$
$FE\to \epsilon$

$S\to XE$
$\to aX{C}_{n}E$
$\to aaX{C}_n{C}_{n}E$
$\to aabY{C}_n{C}_{n}E$
$\to aabbY{C}_b{C}_{m}Z{C}_{n}E$
$\to aabbY{C}_b{C}_m{C}_b{C}_{m}ZE$
$\to aabbY{C}_b{C}_m{C}_b{C}_{m}VE$
$\to aabbY{C}_b{C}_m{C}_{b}V{C}_{m}E$
$\to aabbY{C}_b{C}_{m}V{C}_n{C}_{m}E$
$\to aabbY{C}_{b}V{C}_m{C}_n{C}_{m}E$
$\to aabbYV{C}_n{C}_m{C}_n{C}_{m}E$
$\to aabbY{C}_n{C}_m{C}_n{C}_{m}E$
$\to aabbbY{C}_b{C}_{m}Z{C}_m{C}_n{C}_{m}E$
$\to aabbbY{C}_b{C}_m{C}_{m}Z{C}_n{C}_{m}E$
$\to aabbbY{C}_b{C}_m{C}_m{C}_b{C}_{m}Z{C}_{m}E$
$\to aabbbY{C}_b{C}_m{C}_m{C}_b{C}_m{C}_{m}ZE$
$\to aabbbY{C}_b{C}_m{C}_m{C}_b{C}_m{C}_{m}VE$
$\to aabbbY{C}_b{C}_m{C}_m{C}_b{C}_{m}V{C}_{m}E$
$\to aabbbY{C}_b{C}_m{C}_m{C}_{b}V{C}_m{C}_{m}E$
$\to aabbbY{C}_b{C}_m{C}_{m}V{C}_n{C}_m{C}_{m}E$
$\to aabbbY{C}_b{C}_{m}V{C}_m{C}_n{C}_m{C}_{m}E$
$\to aabbbY{C}_{b}V{C}_m{C}_m{C}_n{C}_m{C}_{m}E$
$\to aabbbYV{C}_n{C}_m{C}_m{C}_n{C}_m{C}_{m}E$
$\to aabbbF{C}_n{C}_m{C}_m{C}_n{C}_m{C}_{m}E$
$\to aabbbcF{C}_m{C}_m{C}_n{C}_m{C}_{m}E$
$\to aabbbccF{C}_m{C}_n{C}_m{C}_{m}E$
$\to aabbbcccF{C}_n{C}_m{C}_{m}E$
$\to aabbbccccF{C}_m{C}_{m}E$
$\to aabbbcccccF{C}_{m}E$
$\to aabbbccccccFE$
$\to aabbbcccccc$