Se una grammatica G è sinistra e destra regolarmente, perché $ || L (G) ||\ Leq || P || $?

Question

Stava studiando teoria automatica e lingue formali e ha trovato questa domanda:

Se una grammatica $ G $ è sinistro e destro regolare, perché $ || L (G) || \ Leq || P || $ ?

Ho cercato la teoria ma mi manca qualcosa. E non riesco a trovare la risposta da nessuna parte, quindi sto chiedendo qui.

Definizioni:

$ p $ = set di regole

Regola regolare di destra: grammatica $ g= (n, t, p, s) $ , una regola è in $ P $ Se la regola è nel modulo: $ a \ raddoppia BA $ $ (A, B \ in n) \ wedge (a \ in t) $

regola regolare a sinistra: grammatica $ g= (n, t, p, s) $ , una regola è in $ P $ Se la regola è nel modulo: $ A \ Randerarow AB $ $ (A, B \ in n) \ wedge (a \ in t) $ .

Grammatica regolare sinistra: una grammatica in cui tutte le regole sono regole regolari.

Grammatica normale-regolare: una grammatica in cui tutte le regole sono regole corrette corrette.

Esempio di un set di regole $ p $ con entrambe le regole regolari e regolari a sinistra: $ P={A \ RightArrow A, B \ Right Danko B \} $

E essendo sia a sinistra, regolare e regolare rendono la grammatica regolari e digita 3

Answer 1

La tua grammatica contiene solo regole del modulo $ a \ a $ , per $ a \ in N $ e $ a \ in T $ .Pertanto $ L (G)={\ Sigma \ in t: s \ to \ sigma \ in p \} $ .Lo prendi da qui.