[Generico] Automa a stati finiti deterministico della concatenazione di un linguaggio non regolare ed uno regolare
Qualcuno saprebbe dirmi qual è il DFA $\mathcal{A} = (Q, {0, 1}, \delta, q_0, F)$ del seguente linguaggio:
$ L = {0^n1^n | n >= 0} @ {0, 1}$\(\displaystyle ^* \),
dove:
$Q$, insieme finito di stati
$\delta : Q \times \Sigma to Q$, funzione di transizione
$q_0 in Q$, stato iniziale
$F sube Q$, insieme degli stati finali
Io avevo pensato allo stesso DFA che riconosce ${0, 1}$\(\displaystyle ^* \), poichè:
[list=1]1) ${0, 1}$\(\displaystyle ^* \) $subset$ $L = {0^n1^nw | n >= 0, w in {0, 1}$\(\displaystyle ^* \) $}$, in quanto basta prendere tutte le x $in L$ aventi $n = 0$ per verificare l'inclusione.[/list:o:32bghmse]
[list=2]2) $L sube {0, 1}$\(\displaystyle ^* \)$=\Sigma$\(\displaystyle ^* \), poichè le stesse stringhe ottenute come concatenazione dei due linguaggi appartengono ancora a ${0, 1}$\(\displaystyle ^* \).
[/list:o:32bghmse]
e quindi $L = \Sigma$\(\displaystyle ^* \).
$ L = {0^n1^n | n >= 0} @ {0, 1}$\(\displaystyle ^* \),
dove:
$Q$, insieme finito di stati
$\delta : Q \times \Sigma to Q$, funzione di transizione
$q_0 in Q$, stato iniziale
$F sube Q$, insieme degli stati finali
Io avevo pensato allo stesso DFA che riconosce ${0, 1}$\(\displaystyle ^* \), poichè:
[list=1]1) ${0, 1}$\(\displaystyle ^* \) $subset$ $L = {0^n1^nw | n >= 0, w in {0, 1}$\(\displaystyle ^* \) $}$, in quanto basta prendere tutte le x $in L$ aventi $n = 0$ per verificare l'inclusione.[/list:o:32bghmse]
[list=2]2) $L sube {0, 1}$\(\displaystyle ^* \)$=\Sigma$\(\displaystyle ^* \), poichè le stesse stringhe ottenute come concatenazione dei due linguaggi appartengono ancora a ${0, 1}$\(\displaystyle ^* \).
[/list:o:32bghmse]
e quindi $L = \Sigma$\(\displaystyle ^* \).
Risposte
Secondo me le considerazioni che hai fatto sono corrette. Si ha difatti che che $L_1 = \{0^n1^n\}$ non è altro che un caso particolare di $L_2 = \{0, 1\}^{\star}$ e pertanto generabile da quest'ultimo 
.
Anche l'automa finale che si ottiene risulta essere molto semplice: bastano due stati uno iniziale ed un altro di accettazione se non erro (ho fatto linguaggi e compilatori molto tempo fa ma credo dovrò riprendere in mano gli appunti perché mi serviranno per la tesi). Andando a memoria non so (ma potrei sbagliarmi) se uno stato possa essere allo stesso tempo iniziale e di accettazione. In tal caso correggimi se sbaglio...
.Anche l'automa finale che si ottiene risulta essere molto semplice: bastano due stati uno iniziale ed un altro di accettazione se non erro (ho fatto linguaggi e compilatori molto tempo fa ma credo dovrò riprendere in mano gli appunti perché mi serviranno per la tesi). Andando a memoria non so (ma potrei sbagliarmi) se uno stato possa essere allo stesso tempo iniziale e di accettazione. In tal caso correggimi se sbaglio...
Grazie per la risposta onlyReferee! 
Cmq l'ultimpo punto della definizione di DFA è la risposta al tuo dubio:
$F sube Q$, quindi, dato che $q_0 in Q$ ed essendo $q_0$ stato iniziale del DFA, automaticamente lo stato iniziale può essere uno stato d'accettazione.
Cmq l'ultimpo punto della definizione di DFA è la risposta al tuo dubio:
$F sube Q$, quindi, dato che $q_0 in Q$ ed essendo $q_0$ stato iniziale del DFA, automaticamente lo stato iniziale può essere uno stato d'accettazione.
Benissimo allora, così l'automa è ancora più semplice in questo caso. Felice di esserti stato d'aiuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo