Dimostrare che l'insieme di linguaggi regolari è un sottoinsieme proprio dell'insieme delle lingue context-free

Question

mi lavavo up (non lavoro) su qualche calcolo-teoria e mai incontrato questo problema:

Come si può dimostrare che l'insieme dei linguaggi regolari è un sottoinsieme proprio dell'insieme dei linguaggi context-free.

Ora so un linguaggio è regolare se e solo se è accettato da un automa a stati finiti.

E so che una lingua è context-free se e solo se è accettato da un Pushdown automa.

Ma io non sono sicuro di quale soluzione è.

Answer 1

Qualsiasi DFA è equivalente ad un PDA, che succede a non spingere nulla sulla sua risma, quindi, tutti i linguaggi regolari sono anche context-free. Più formalmente:

A DFA è definito come un 5-tupla (S, S, s0, d, F) costituito dell'alfabeto d'ingresso, insieme di stati, Stato, tavolo di transizione, e insieme di (accettare) stati finali iniziare.

Un PDA è definito come un 7-tupla, compresi tutti gli elementi di un DFA, più due ulteriori parametri: y (l'alfabeto pila) e Z (il simbolo iniziale stack). Una tabella transizione PDA è leggermente diversa da una tabella di transizione DFA: ogni transizione può dipendere sia il simbolo di ingresso e il simbolo stack corrente, e le transizioni possono spingere o pop dalla pila.

Quindi, con l'introduzione di un alfabeto fittizio pila composta da un unico simbolo, è banale (anche se un po 'fastidioso e prolisso di scrivere!) Per mappare la tabella di transizione di DFA (state, input) -> state ad un equivalente transizione PDA tavolo (state, input, stack) -> (state, stack).

Per completare la prova di un corretto rapporto sottoinsieme: esistono lingue che sono context-free, ma non regolare, in modo che i linguaggi regolari costituiscono un sottoinsieme proprio dei linguaggi context-free. Esempio:. La lingua di stringhe composte da parentesi bilanciate