[Linguaggi Formali e Compilatori] Automa unione Ling tipo 2 e Ling tipo 3

[Korost1]

Chiedo venia per la stupidità della domanda, ma non riesco proprio a capire

Se ho L1 = { a* c\(\displaystyle ^n \) b\(\displaystyle ^m \) c\(\displaystyle ^(n-m) \) | n > m > 0} ed è di tipo 2 (o mi sbaglio totalmente?) e quindi devo fare un automa a pila.
e L2 = { a* (c\(\displaystyle ^n \) b) aa d | n > 0) } che è di tipo 3 (o mi sbaglio totalmente anche in questo caso?). Faccio un automa a stati finiti per il linguaggio di tipo 3.

Come li unisco questi due automi? normalmente come se fossero due automi di tipo 2? o devo fare anche per L2 un automa a pila per poterli unire?

[Branko1]

Non vorrei dire una cavolata, è già un po che ho passato questo esame, ma il primo non dovrebbe essere di tipo 2 e si vede usando il pumping lemma. Prendiamo una stringa del linguaggio 'accbc' e parametrizziamola :

$
uv^iwx^iy,
|vwx| <= n,
|vx| >= 1,
$

ora

$
u = a,
v = c c,
w = O/,
x = b,
y = c,
$

Se iteriamo facciamo per i = 2 viene fuori

accccbbc

Ma l'ultima c dovrebbe essere $ c^(n-m) $ quindi $ c^(4-2) = c c $.
Quindi la stringa non appartiene al linguaggio in quanto dovrebbe terminare con due c. Questo dovrebbe appunto dimostrare che il linguaggio non è di tipo 2.

[Korost1]

non ho capito :O ad occhio mi sembra ben che è ben parentesizzata e c'è relazione tra m e n quindi di tipo 2 se non è ambigua o non ho capito assolutamente nulla nemmeno delle basi? xD

[Branko1]

Guarda il pumping lemma è una cosa che anche io ho messo un po a recepire, devi immaginarla come un ciclo for.

Prendo un esempio più semplice $ a^n b^n c^n $, il pumping lemma dice (presa da wikipedia)

Dato un linguaggio L context-free, esiste una costante intera positiva n con la seguente proprietà. Sia z ∈ L con |z| ≥ n; allora si può suddividere $z = uvwxy$ con $|vwx| ≤ n, |vx| ≥ 1$ tali che, per ogni i≥0, $uv^i wx^iy$ appartiene a L

Applichiamolo, prendiamo una stringa del linguaggio $ z = a a b b c c $ e scomponiamola :

$u = O/ $
$v = a a$
$w = b b$
$x = c c$
$y = O/ $

NB con $O/ $ intendo una stringa vuota.

dunque il pumping lemma di tipo 2 dice che $ z = uv^iwx^iy $ deve sempre appartenere al linguaggio in quanto deve esistere una parte del linguaggio ripetibile un numero arbitrario di volte ottenendo una stringa valida. Quindi prendiamo la stringa
$uv^2 wx^2y$

otteniamo

$ v = a a a a $
$ w = b b $
$ x = c c c c $

Quindi $z = a a a a b b c c c c$ che non appartiene al linguaggio L perché sappiamo che tale linguaggio deve avere un numero uguale di a, b e c.

Dunque abbiamo fornito una prova che il linguaggio non è di tipo 2 (e neanche tipo 3 ovviamente).

Metti caso avessimo ottenuto una stringa del linguaggio (per esempio $a^n b^n$) non avremmo dimostrato che il linguaggio è di tipo 2, in quanto il lemma si usa come condizione base ma non sufficiente.

PS
Anche il secondo ad occhio non mi sembra regolare, e forse neanche libero dal contesto.