Questa lingua è normale o no?

Question

Ho la lingua {4 ^ (w⋅g) 34 ^ (g) | w, g ∈nat} sopra l'alfabeto {0,1}.

Ho bisogno di scoprire se questa lingua è riconoscibile, decidabile, contesto gratuito, regolare o nessuno di questi.

Come dovrei andare a farlo o sapere?

Grazie

Answer 1

Considera qualsiasi stringa del modulo 4^a 3 4^b. Possiamo trovare w, g per il nostro a, b? Bene, sappiamo che g deve uguale a b uguali, e quindi possiamo scegliere w = a + g. Poiché a, b e g sono numeri naturali, quindi deve essere w; La risposta è che, sì, per qualsiasi stringa del modulo 4^a 3 4^b, abbiamo una stringa nella tua lingua.

La lingua di tutte le stringhe del modulo 4^a 3 4^b è descritta dall'espressione regolare 4* 3 4* e, in quanto tale, la lingua è normale, il contesto gratuito, decidabile e riconoscibile.

Supponiamo che la tua lingua non fosse regolarmente; Come hai potuto dire? È possibile utilizzare il teorema di MyHill-Nerode o il lemma del pompaggio per le lingue regolari per derivare una contraddizione dal presumere che la lingua fosse regolare.

Supponiamo che la tua lingua non sia priva di contesto. È possibile utilizzare il lemma del pompaggio per le lingue senza contesto per derivare una contraddizione dal presumere che la lingua fosse priva di context.

Certo, se la tua lingua non era decidabile o riconoscibile, è possibile dimostrare che anche in vari modi.