Let's do one more bit of practice
converting non-deterministic machines to deterministic ones.
Here I've written a non-deterministic machine.
It has ambiguity.
Right in state 1 there are 2 ways to go on a.
It also has epsilon transitions,
and I'll start making its deterministic equivalent down here.
Well, when we enter the non-deterministic machine,
we could only be in state 1, but after that we could see an a,
and if I see an a I could be in 2, 4,
or I could take the free epsilon transition to 5,
or I could keep going and take the free epsilon transition to 6.
I'll label my new state 2456
because it keeps track of everywhere that I could have my fingers
if I'm simulating this non-deterministic machine.
Now, should this state be an accepting state or not?
Well, remember that a finite state machine accepts if there's any path
to an accepting state, and 6 is one of our accepting states.
Because the original machine could accept a,
a, epsilon, epsilon, win, we want our new machine to also accept a.
A, win.
In my converted world, the state accepts if any of its corresponding
original states also accept.
Let's say that I'm in either 2, 4, 5, or 6 and I see a c.
If I'm in 2 and I see a c, I fall off the world.
If I'm in 4, fall off the world.
5, I go to 6, looking good.
6, fall off the world.
Here if I was in 2, 4, 5, or 6 and I see a c,
I end up just in state 6, and that's definitely an accepting state.
Now, there's some other ways to get out of 2, 4, 5, and 6,
and when we do, we might be in states 2 or 3.
Since 3 is an accepting state up there,
2 or 3 is an accepting state down here.
If I'm in 2 or 3, on a b from 2 I go to 3,
and c I'd fall off the world, so we'd end up in state 3.
If I'm in 2 or 3 and I see a c,
I must really have been in state 3, and I stay in state 3,
so either on b or c we end up in just state 3,
which is also an accepting state.
And if I'm in state 3, there's a self-loop back to state 3.
Now, I've filled out almost all of this deterministic equivalent.
But I forgot to label an edge.
Help me out.
As the quiz, what should the label for this edge be
so that this deterministic equivalent and this non-deterministic machine
accept exactly the same language?
Facciamo pratica
nel convertire le macchine non-deterministiche in deterministiche.
Ho scritto qui una macchina non-deterministica.
c'è ambiguità al suo interno.
Dallo stato uno ci sono due vertici che escono con 'a'.
Ci sono inoltre epsilon transizioni,
comincerò a costruire il suo equivalente deterministico qui sotto.
Bhé, quando accendiamo la macchina non-deterministica,
non possiamo che essere allo stato uno, dopo questo potremmo vedere una 'a' ,
e se vedo una 'a' potrei essere in due o quattro,
o prendere la epsilon gratis ed arrivare a cinque.
O continuare e prendere la epsilon gratis fino a sei.
Chiamerò questo nuovo stato '2456'
poiché tiene traccia di ovunque possa andare il mio dito
se simulassi questa macchina non deterministica.
Adesso, questo stato dovrebbe essere accettante o no?
Bhé, ricordate che una macchina a stati finiti accetta l'input se c'è un qualsiasi percorso
che raggiunge uno stato accettante, e il sei è uno stato accettante.
La macchina, in origine, poteva accettare 'a' ,
'a' , epsilon, epsilon, accetta. Vogliamo che la nostra macchina accetti anche 'a' .
'a', accetto.
Nel mio mondo convertito, lo stato è accettante se almeno uno dei corrispondenti
stati originali è accettante.
Diciamo che sono in due, quattro,cinque o sei e vedo una 'c' .
Se sono in due e vedo una 'c' , la macchina si interrompe.
Se sono in quattro, si interrompe.
Cinque, vado in sei, sembra buono.
sei, si interrompe.
Quindi se sono in due, quattro,cinque o sei e vedo 'c' ,
finisco in sei, che è uno stato accettante.
Adesso, c'è un altro modo per uscire da due, quattro, cinque e sei,
e se usciamo, potremmo essere nel due o nel tre.
Visto che tre è uno stato accettante,
tre lo è anche qui sotto.
Se sono in due o tre, e vedo una 'b', da due vado a tre,
con 'c' terminerei, quindi finiamo nello stato tre.
Se sono in due o tre e vedo 'c' ,
devo per forza essere nello stato tre, e lo sono,
quindi con 'b' o 'c' finiamo nello stato tre,
che è anch'esso accettante.
E se sono in tre, c'è un self-loop in tre.
Adesso ho quasi completato gli stati dell'equivalente deterministico.
Ho dimenticato di assegnare un'etichetta ad un vertice.
Aiutatemi.
Come quiz vorrei che poneste questo vertice,
così che l'equivalente deterministico e la macchina non-determinisitica
accettino lo stesso linguaggio.
非決定性有限状態機械を
決定性有限状態機械にもう一度変換してみましょう
ここに非決定性有限状態機械を書きました
あいまいさを含んでいます
ステート1からaが入力された時に
遷移先が2つあります
イプシロン遷移も見られます
この下に決定性有限状態機械を書きましょう
非決定性有限状態機械では
開始ステート1からaを入力すると
ステート2かステート4へ遷移することができます
もしくはイプシロンでステート5へも遷移できます
そのままイプシロン遷移を使い
ステート6への遷移も可能です
よって新しいステートを2456とします
今指を置いたすべての場所が
非決定性有限状態機械で行けるステートです
このステートは受理ステートでしょうか?
非決定性有限状態機械では受理ステートへ行く道が
1つでもあれば受理してくれます
元の非決定性有限状態機械ではaのあと
イプシロン、イプシロンと遷移してaを受理します
決定性有限状態機械でも同じ結果が必要です
非決定性有限状態機械で対応するステートが
1つでも受理ステートならば
そのステートは受理ステートとなります
ステート2、4、5もしくは6にいて
cを入れるとします
ステート2でcを入れるとそこで終了です
ステート4でも同じ結果です
ステート5ではステート6に行けます
ステート6でも終了してしまいます
ステート2、4、5もしくは6にいてcを入れると
受理ステートであるステート6に遷移します
ステート2、4、5、6からの他の遷移もあります
ステート2、3へ遷移する方法です
元の非決定性有限状態機械で
ステート3が受理ステートですので
このステート2、3は受理ステートです
ステート2からbが入力されると
ステート3に遷移します
ステート3からbだと終了します
ステート2か3でcを入れると
元の有限状態機械でステート3にいたはずで
ステート3に戻ってきます
よってbを入れてもcを入れても
受理ステートである
ステート3にたどり着くのです
ステート3にいたとしたら
セルフループでステート3に戻ります
これで決定性有限状態機械はほぼ完成ですが
エッジのラベルを忘れていました
皆さん考えてみてください
この決定性有限状態機械を
非決定性有限状態機械と同じように作用させるには
エッジのラベルをどうすべきでしょうか?
Vamos praticar mais uma vez.
a conversão de autômato finito não determinista para um determinista.
Desenhei aqui um autômato finito não determinista.
Ele tem ambiguidade.
Aqui, no estado 1, exsitem duas maneiras de ler `a'.
Ele tem também transições epsilon.
Vou começa a desenhar seu equivalente determinista aqui.
Quando entramos no autômato não determinista,
apenas podemos estar no estado 1. Mas, então podemos ver um `a',
e nesse caso podemos ir para 2, 4,
ou tomar a transição epsilon para 5,
ou ainda prosseguir por esta transição epsilon para 6.
Vou então chamar meu novo estado de 2456,
porque ele representa todos os estados para onde posso ir,
se eu estiver simulando este autômato não determinista.
Este estado deveria ser de aceitação, ou não?
Bem, lembre-se que um autômato dinito aceita, se existe ALGUM caminho
para um estado de aceitação, e 6 é um estado de aceitação.
Como o autômato original aceita -- `a',
`a', epsilon, epsilon, ok -- nosso novo autômato também aceita -- `a',
`a', ok.
No meu mundo convertido, um estado é de aceitação se algum dos seus correspondentes
estados originais é de aceitação.
Digamos que eu esteja em 2456, e vejo `c'.
Se estou em 2 e vejo `c', falho.
Se estou em 4 e vejo `c', falho.
De 5, vou para 6 -- ok.
De 6, falho também.
Então aqui, se estou em 2456, e vejo `c',
ou apenas para o estado 6, e este é um estado de aceitação.
Existem outras maneiras de sair de 2456,
e quando fazemos isso, podemos ir para os estados 2 ou 3.
Como 3 é um estado de aceitação,
23 é um estado de aceitação.
Se eu estou em 23 e vejo `b', de 2 vou para 3,
e de 3 falho. Portanto terminamos neste estado 3.
Se estou em 2 ou 3 e vejo `c',
então eu deveria estar no estado 3, e permaneço no estado 3.
Portanto, tanto com `b', como com `c', vou para o estado 3,
que é também um estado de aceitação.
E se eu estou no estado 3, há um loop aqui, de volta para 3.
Agora já quase fiz quase tudo deste determinista equivalente,
mas me esqueci de rotular um arco.
Então me ajude aqui.
Como exercício, como você deve rotular este arco,
de modo que este autômato determinista e este outro não determinista
aceitem exatamente a mesma linguagem?