(a)  Vedi testi.

(b) 

00(0+1)*  + (0+1)*110

S -> 0A | 0B | 1B | 1F
A -> 0 | 0L | 1L
L -> 0 | 1 | 0L | 1L
B -> 0B | 1B | 1F
F -> 1G
G -> 0

Questo se vogliamo attenerci strettamente alla definizione
di grammatica regolare. Si possono ovviamente dare delle
grammatiche alternative, ma occore pero' dire che tali grammatiche 
sono equivalenti a quelle regolari.


(c)

Per vedere che il primo linguaggio e' regolare, forniamo
un'espressione regolare che lo rappresenta.
Lo facciamo per un k piccolo, K=2. Si puo' vedere facilmente
che si puo' ottenere un'espressione regolare se prendiamo
un k qualsiasi.

aa(a)*bb(b)*

Il secondo non e' regolare. 
Basta fare un ragionamento simile a quello che si usa per il il pumping lemma.
Se esistesse un automa a stati finiti che riconosce il linguaggio,
allora prendiamo la stringa a^kb^n^c^m con n maggiore del numero di
stati dell'automa. Il riconoscimento di tale stringa ci porterebbe ad
attraversare almeno due volte lo stesso nodo durante la scansione
della parte b^n, facendo quindi riconoscere dall'automa anche 
stringhe a^kb^(n+hq)^c^m dove h e' arbitrario e q e' il numero di nodi
del ciclo. L'automa riconoscerebbe quindi anche stringhe che non rispettano
il vincolo n<=m, assurdo.