These easy-to-write FSMs that we've been using
that involve epsilon transitions or ambiguity--
remember, ambiguity means that I can go to 2 different places on the same input--
are formerly known as non-deterministic finite state machines.
Non-deterministic here just means that you may not know exactly
where to go or where to put your finger.
It's not lock-step. You have choices.
You have freedom.
A lock-step FSM with no epsilon transitions
and no ambiguity by contrast is called a deterministic finite state machine.
Everything is determined from the start.
Given the finite state machine and the input, you always know
exactly what will happen.
Our finite state machine simulation procedure can handle
deterministic finite state machines.
That makes them really useful for implementing regular expressions
under the hood.
Let me just show you an example of this non-determinism just to drive it home.
Suppose we were back here in this previous finite state machine,
but now the input is 1-23.
Where are we?
We started here, and on a 1 we went here,
and then I guess if we're supposed to stay alive and there's a hyphen,
we must have gone here and taken the hyphen.
And now there's a 2, but now this is really not obvious.
I could stay here on this self-loop for a 3,
or I could have gone back on this free epsilon transition
and done the self-loop here on a 3, so I could be in state 2 or state 5.
Since there isn't one single answer for where I could be,
this is non-deterministic.
As a bit of a fun aside, this notion of determinism
or non-determinism can be related to the question of free will in philosophy.
Can we actually make independent choices?
Or is everything preordained by the current state of the world
and forces acting on it, like a lock-step game of billiards or snooker or pool?
Some philosophers will approach this by suggesting that we have
the illusion of free will--that's a disconcerting thought--
which is handy for describing subjective experience.
We certainly often feel like we have free will.
Regardless of what's going on in the real world,
we're going to see that something similar holds
for finite state machines.
Although non-deterministic finite state machines look like they have
much more power and much more freedom,
anything that could be done with them could also be done
in our deterministic billiard ball world.
In fact, you can watch me suck free will out of this world right now.
Every non-deterministic finite state machine
has a corresponding deterministic finite state machine
that accepts exactly the same strings.
Non-deterministic finite state machines are not any more powerful
than deterministic finite state machines.
They're just more convenient.
It's easier to write them down.
Let's see an example of this extraordinary claim.
Suppose we have this regular expression.
There are only 2 strings in the language of this regular expression,
but here I've drawn out a very elaborate finite state machine for it
that has epsilon transitions coming out the wazoo.
This is very non-deterministic.
We definitely need to see an a, but then here these 2 epsilon transitions
represent the explicit choice.
Do I do the b, or do I skip over it?
On the top road, we need to see the b.
On the bottom road, we skip entirely past it.
And then in any event, we need to see the c.
I'm now going to write a deterministic finite state machine
that does exactly the same thing, and I'm going to hint at
how this conversion works.
We'll see this again in just a minute.
After I see an a, I could be in 2,
or I could take the epsilon to 3.
I could have taken the epsilon down here to 6
or all the way over to 4, so there are 4 places
I could be in.
That's a lot of fingers.
I'll just record all of them as the name for my new state, 2364.
From here, if I see a b and I survive--remember, finite state machines work
if there's any path that gets to the end--it must have been that I was in state 3,
at which point now I'm just in state 4.
By contrast, if I was back here and I saw a c,
it must have been that I was in state 4, and now I'm in state 5.
And then finally, if I'm in state 4 and I see a c,
I end up here, so this deterministic finite state machine
accepts the same language as the one above.
The 2 strings, a, b, c, and a, c
are both in it, but it does not have
epsilon transitions or ambiguity.
In any particular node, there are never 2 edges going out labeled a,
and there are never epsilon transitions.
Let's see another example of how this works.
Again, I'm going to build a deterministic machine
where every state in the deterministic machine
corresponds to a set of states
in the non-deterministic one.
Again, to restate that, you give me a non-deterministic machine,
I'm going to build you a deterministic machine d
that accepts the same language, and the way I'll do it is
every state in d is going to correspond to a set of states
in the non-deterministic machine you gave me.
Queste semplici da scrivere FSM che stiamo usando
coinvolge le transizioni epsilon ovvero l'ambiguità --
ricordate: ambiguità significa che posso andare in due posti differenti con lo stesso input --
sono dette macchine a stati finite non-deterministiche.
Non-deterministiche significa qui che potreste non sapere con esattezza
dove andare, ovvero dove posare il dito.
I passi non sono tutti definiti. Avete delle scelte.
Avete libertà.
Una macchina senza passi definiti, senza epsilon transizioni
e senza ambiguità è chiamata macchina a stati finiti deterministica.
Tutto è determinato dall'inizio.
Data la macchina e l'input, saprete sempre
esattamente cosa succederà al suo interno.
Il nostro simulatore di macchine a stati finiti può gestire
macchine deterministiche.
Questo lo rende molto utile per implementare le espressioni regolari
dietro le quinte.
Lasciatemi fare un esempio di questo non-determinismo per capirlo meglio.
Supponete di essere ancora con questa macchina a stati finiti,
ma adesso l'input è '1-23' .
Dove siamo?
Cominciamo da qui, e con '1' andiamo qui,
e poi se siamo ancora in vita probabilmente vedremo un trattino,
dobbiamo per forza essere passati di qua ed aver incotrato un trattino.
E adesso c'è un '2' , e non è così ovvio.
Posso rimanere qui per un self-loop con '3' ,
o posso andare indietro e riprendere questa epsilon gratis
e posso fare un self-loop qui con un '3'; potrei essere nello stato due o nel cinque.
Se non c'è una sola risposta per dove potrei essere,
allora il percorso è non-deterministico.
Con un po' di contorno di divertimento, queste nozioni di determinismo
o non-determinismo possono essere associate alla questione del libero arbitrio in filosofia.
Possiamo compiere scelte indipendenti?
O è tutto preordinato dallo stato corrente del mondo?
e dalle forze agenti su di esso, come un gioco in sequenza come lo snooker o il biliardo?
Alcuni filosofi avvicinano questo problema suggerendo che
viviamo l'illusione del libero arbitrio -- pensiero sconcertante --
poiché è utile per relazionarci con l'esperienza soggetiva.
Spesso sentiamo di avere il libero arbitrio.
Senza preoccuparci di quello che succede nel mondo reale,
vedremo che un approccio del genere tiene anche
parlando di macchine a stati finti.
Anche se le macchine non-deterministiche sembrano concedere molto più
potere e molta più libertà,
tutto ciò che può essere fatto con loro, può essere fatto anche
nel nostro "mondo deterministico nella palla da biliardo" .
Infatti, potete vedermi estorcere libero arbitrio da questo mondo proprio in questo momento.
Ogni macchina non-deterministica a stati finiti
ha una corrispondente macchina deterministica a stati finiti
che accetta esattamente le stesse stringhe.
Le macchine non-deterministiche non sono affatto più potenti
di quelle deterministiche.
Sono solo più convenienti.
E' facile dimostrarlo.
Vediamo un esempio di questa straordinaria attestazione.
Supponete di avere questa espressione regolare.
Ci sono solo due stringhe nel linguaggio di questa espressione regolare,
ma qui ho disegnato una macchina molto elaborata per rappresentarlo,
che ha epsilon transizioni che gli sbucano dappertutto.
Questa macchina è molto non-deterministica.
Dobbiamo per forza vedere una 'a' , ma poi qui due transizioni epsilon
rappresentano la scelta esplicita.
Vado alla 'b' o passo oltre?
La strada superiore, dovremmo in incontrare una 'b' .
Su quella inferiore, saltiamo direttamente.
In ogni caso vedremo 'c' .
Scrivo ora una macchina deterministica
che faccia esattamente la stessa cosa, e sottolineerò
come avviene questa conversione.
Lo vedremo in un momento.
Dopo aver visto una 'a' , potrei essere in due,
o posso prendere la epsilon ed essere in tre.
Potrei avere preso la epsilon qui ed essere in sei
o fino in fondo ed essere in quattro; quindi ci sono quattro posti
in cui potrei essere.
Sono un sacco di dita.
Registrerò il nome del mio nuovo stato '2364' .
Da qui, se vedo una 'b' e sopravvivo -- ricordate che una macchina a stati finiti esiste solo
se c'è un qualunque percorso sino alla fine -- significa che dovrei essere nello stato tre,
dal quale posso solo passare al quattro.
Al contrario, se fossi ancora qui e vedessi una 'c' ,
potrei essere allo stato quattro, e quindi vado al cinque.
Infine, se sono allo stato quattro e vedo una 'c' ,
finisco con l'essere qui; quindi questa macchina deterministica accetta
lo stesso linguaggio di quella non-deterministica.
Le due stringhe 'abc' e 'ac'
ci sono entrambe, ma non ci sono
epsilon transizioni né ambiguità.
In ogni nodo, non ci sono mai due vertici uscenti con 'a' ,
e neanche epsilon transizioni.
Vediamo un altro esempio di come funziona.
Ancora, mi appresto a costruire una macchina deterministica a a stati finiti
dove ogni stato della macchina deterministica
corrisponde ad un insieme di stati
in quella non-deterministica.
Ancora, riformulando, abbiamo una macchina non-deterministica e
ne costruiremo una deterministica 'D'
che accetta lo stesso linguaggio. Comincerò facendo
corrispondere ad ogni stato in 'D' un insieme di stati
della macchina non-deterministica che avevo all'inizio.
イプシロン遷移とあいまいさを含む
有限状態機械を使ってきましたね
あいまいさとは同じ入力で違う場所へ行くことです
これらは非決定性有限状態機械と呼ばれています
ここで使われている非決定性という言葉は
行き先が定かではないととらえ
一手一手定められた場所にしか行けないのではなく
行き先を選択できることです
イプシロン遷移がなく
遷移先の定まった有限状態機械は
決定性有限状態機械と呼ばれ
始めから道筋が決まっています
有限状態機械と入力だけで
結果はすべて分かります
FSMシミュレータで作業できるのは
決定性有限状態機械です
機械の中で正規表現を実装するのに
とても役立ちます
それでは非決定性有限状態機械の例を
お見せしましょう
先ほどの問題を使いましょう
ただ入力を1-23に変えます
現在のステートはどこでしょう?
開始ステートから始まります
ここに遷移したとして次はハイフンですので
その場合ステート4に遷移しますね
2で遷移し次がはっきりしません
セルフループで留まることもできますが
イプシロン遷移で戻ることも可能です
ステート2にいることも
ステート5にいることもできるのです
1つに答えを絞ることができないので
非決定的となるのです
余談になりますが決定性と非決定性という概念は
哲学の自由意思説に基づいて作られています
私たちは個人の意思だけで決断できますか?
それともビリヤードのような
一手ずつ進むゲームのように
現状の世界の中で
すでに定められているものでしょうか?
混乱を招く意見かもしれませんが
自由意思はただの錯覚だという哲学者もいます
主観的な経験については役立つ意見ですが
周りで何が起きていようとも
私たちには自由な意志があると信じられています
有限状態機械に対しても
このような考えが見られます
非決定性有限状態機械の方が
多くのことができると思われがちですが
非決定性有限状態機械で起こり得るすべてのことを
決定性有限状態機械でも起こせます
今から自由意思を取り除く作業をしたいと思います
いかなる非決定性有限状態機械にも
同じ文字列を受理する
決定性有限状態機械が存在し
同じ文字列を受理します
非決定性有限状態機械の方が
決定性有限状態機械に比べて
パワフルということではないのです
より便利に作られているだけです
実践して説明します
この主張を例にしてみましょう
正規表現をこのように設定します
これでは2つの文字列しか受理しません
しかし有限状態機械は入り組んだものにしました
たくさんのイプシロン遷移があります
これは非決定的です
aから始まったあとで2つのイプシロン遷移が
明確に選択肢を表しています
bを入れるかスキップするという選択肢です
上の方法ではbを入れ進みます
下の方法ではその行程をスキップします
最終的にはcが必要です
では今度はこの非決定性有限状態機械
同じことをする
決定性有限状態機械を書いてみます
どのように変更すべきでしょうか
このあとにお見せします
イプシロンでステート3へ遷移できます
このイプシロンはステート6へも遷移可能です
もしくはステート4へ遷移も可能ですので
合計4ヶ所へ遷移できます
指がたくさん必要です
すべてを新しいステートの名前として記録します
有限状態機械は最後まで行く道があれば
受理しますね
そのためbを入れて遷移することができたら
ステート3にいたことになります
その場合ステート4へ進むことができます
cで遷移できるとするとステート4にいたことになり
ステート5へ遷移することになります
ステート4にいてcが入力されれば
決定性有限状態機械でも
上記の非決定性有限状態機械と
同じ結果が得られるのです
2つの文字列a、b、cとa、cはありますが
イプシロン遷移とあいまいさは
含まれていません
aのラベルを持つエッジは1つしかなく
イプシロン遷移はできません
他の例を使いどう作用するか見ましょう
もう一度決定性有限状態機械を作ります
この決定性有限状態機械の各ステートは
非決定性有限状態機械のステートの集合に
対応するように設定します
言い換えると非決定性有限状態機械がまず必要で
同じ言語を受理する
決定性有限状態機械Dを作ります
文字列を受理し
決定性有限機械Dの各ステートを与えられた
非決定性有限機械のステートの集合に対応させます
Esses FSMs mais fáceis de definir, que agora estamos usando,
que contêm transições epsilon ou ambiguidade --
lembre-se que ambiguidade significa que eu posso ir para dois lugares distintos com a mesma entrada --
são formalmente chamados de autômatos de estados finitos não deterministas.
Não determinismo aqui significa que você pode não saber
para onde ir.
Não é um estado sem saída. Você tem escolhas.
Você tem liberdade.
Um FSM sem transições epsilon
e sem ambiguidade é chamado de autômato de estados finito determinista.
Tudo é determinado, a partir do estado incial.
Dados o autômato de estados finito e a entrada, sempre é possível saber
exatamente o que vai acontecer.
Nosso simulador de FSM é capaz de tratar
autômatos deterministas.
Por isso ele é muito útil para a implementação de expressões regulares
internamente.
Dexe-me mostrar um exemplo deste não determinismo, como ilustração.
Vamos voltar a este FSM aqui,
mas agora e entrada é 1-23.
Onde estamos?
Começamos aqui e, com `1', vamos para cá,
e então, se quero reconhecer um hífen, devo vir para cá, onde há um hífen --
temos que pegar um hífen --
e agora temos um 2, mas agora não é muito óbvio.
Posso ficar aqui, neste loop, com `3',
ou voltar, através desta transição epsilon,
e fazer este loop aqui, com `3'. Então podemos estar no estado 3 ou no 5.
Como não existe uma única resposta sobre onde eu estaria,
isso é não determinista.
Como um comentário à parte, essa noção de determinismo,
ou não determinismo, está relacionada à questão do livre arbítrio, em filosofia.
Podemos de fato fazer escolhas independentes?
Ou tudo é pré-determinado pelo estado corrente do mundo,
e nos força a agir sobre ele, como em um jogo de bilhar ou de poker?
Alguns filósofos abordam essa questão sugerindo que temos
a ilusão de livre arbítrio -- esse é um pensamento desconcertante --
que é adequado para descrever experiência subjetiva.
Certamente temos a sensação de ter livre arbítrio,
independentemente do que acontece no mundo,
Algo similar ocorre com
autômatos de estados finitos.
Embora autômatos de estados finitos deterministas pareçam ter
muito mais poder e muito mais liberdade,
qualquer coisa que pode ser feita com eles também pode ser feita
em nosso mundo determinista do jogo de bilhar.
De fato, você vai ver que posso mostrar isso agora mesmo.
Todo autômato finito não determinista
tem um autômato finito determinista correspondente,
que aceita exatamente os mesmos strings.
Autômatos finitos não detemrinistas não são mais poderosos
do que autômatos finitios deterministas.
Eles são apenas mais convenientes.
É mais fácil projetá-los.
Vejamos um exemplo disso.
Suponha que temos esta expressão regular.
Existem apenas 2 strings na linguagem desta expressão regular.
Desenhamos aqui um FSM bastante elaborado para esta expressão,
que tem várias transições epsilon.
Ele é bastante não determinista.
Nós queremos reconhecer um `a', mas estas 2 transições epsilon aqui
representam uma escolha.
Escolho esta, com `b', ou pulo por aqui ?
Na rota de cima, temos que ver um `b'.
Na rota inferior, o ignoramos completamente.
E em qualquer caso eu preciso ver um `c'.
Vou desenhar agora um autômato determinista
que faz exatamente a mesma coisa. E vou dar uma dica
de como essa conversão funciona.
Veremos isso novamente daqui a pouco.
Depois de ver um `a', eu posso estar em 2
ou posso tomar a transição epsilon para 3.
Eu poderia também tomar a transição epsilon para 6,
ou ainda prosseguir para 4. Existem portanto três possíveis
lugares onde eu poderia estar.
Um bocado de lugares.
Vou simplesmente registrar todos eles como um novo estado 2364.
Daqui, se eu vejo um `b' e sobrevivo -- lembre-se que um FSM
continua se existir algum caminho que o leva até o final -- eu só poderia ter ido para o estado 3,
e dai para o estado 4.
Por outro lado, se eu estou aqui, e vejo um `c',
então eu só poderia ter ido para o estado 4 e daí vou para o 5.
Então, finalmente, se estou no estado 4, e vejo um `c',
eu termino aqui. Portanto, este autômato determinista
aceita a mesma linguagem que este aqui acima.
Os dois strings `abc` e `ac`
são ambos aceitos, mas este FSM
não tem transições epsilon ou ambiguidade.
De nenhum estado existem 2 arcos saindo, com rótulo `a'
e também não há transições epsilon.
Vejamos um outro exemplo de como isso funciona.
Novamente, vou construir um autômato determinista,
tal que cada estado desse autômato determinista
corresponde a um conjunto de estados
do autômato não determinista.
Em outras palavras, se você me dá um autômato finito não determinista,
eu posso construir uma autômato determinista D
que aceita a mesma linguagem. A maneira de fazer isso é
que cada estado em D corresponde a um conjunto de estados
do autômato não determinista que você me deu.
这些容易编写的有限状态机,我们已经在使用
包含epsilon 转换或者歧义
记住,歧义表示对于同一个输入我可以去两个不同的地方
正式来说,被称作非确定性有限状态机
这里的非确定性只是意味着你可能不是明确地知道
要去哪里或者把你的手指放在哪里
这不是锁死的,你可以做选择
你能自由地选择
相反,没有epsilon转换和没有歧义
的锁死的FSM被称为确定性有限状态机
一切从一开始就决定了
已知有限状态机和输入,你总会明确知道
将要发生的事情
我们的有限状态机模拟函数能够处理
确定性有限状态机
这使它们对于实现正则表达式
真的很有用
让我给你们看一个非确定性有限状态机的例子
假设我们回到这前一个有限状态机
但是现在输入的是1-23
我们在哪里?
我们从这里开始,遇到1,我们移到这里
我想如果我们应该还“活着”,且遇到了连字符
我们必须来到这里接受这连字符
接着是2,但现在这真的不明显
因为到了3,我可以自循环回这里
或者我可能回到这个epsilon转换
并且在遇到3时,结束这个自循环,所以我可以在状2或者状态5
因为我可以得到不止一个答案
这就是非确定性
除了有点有趣之外,确定性和非确定性
的概念与哲学上关于自由的问题联系起来
我们真的可以做独立的选择吗?
或者说是不是一切都是由世界的当前状态和强加于其上的力量
注定的,就好像是一场注定结果的桌球游戏那样?
一些哲学家声称我们有着对自由意志的幻想
--这是一种令人不安的想法--
这种幻想能方便地描述主观的体验
我们肯定经常感觉我们有着自由意志
无论在真实世界里发生什么事情
我们将会看到一些类似的东西对
有限状态机也适用
尽管非确定性有限状态机看起来
有着更多的力量和更多的自由
但是任何能用它们完成的事情,也可以
在我们的确定性有限状态机来实现
In fact, you can watch me suck free will out of this world right now.
每一个非确定性有限状态机
都有着对应的确定性有限状态机
来接受完全一样的字符串
非确定性有限状态机不比
确定性有限状态机强大多少
它们 只是更加方便罢了
编写它们更加容易
让我来看一个关于这个特别声明的例子
假设我们有这个正则表达式
在这个正则表达式里只有两个字符串
但这里我画出了对应它的一个非常复杂的有限状态机
有着epsilon转换
这是非确定性的
我们肯定需要看到a,但这里这两个epsilon转换
代表明确的选择
我要选择b,还是要跳过它呢?
在上面的路线,我们需要看到b
在下面的路线,我们完全跳过它
接着无论怎样,我们需要看到c
现在我将画出一个确定性有限状态机
它能实现完全一样的功能,我将提到
这个转换是怎样进行的
我们将很快看到这个
在看到a之后,我可以在状态2
或者我执行epsilon转换,移到状态3
我可以执行epsilon转换而来到状态6
或者一直到状态4,所以我可以处在
4个状态里
那真的是很多”手指“
我只要将他们记下为我的新状态,2364
这里,如果我看到了b,那就能”活下“了 -- 记住,如果有着任意路线
能去到结尾,那么这个有限状态机就起作用,我之前一定在状态3
现在我就在状态4
相反,如果我返回这里,我看到c
那一定是我之前在状态4,现在我到了状态5
最后,如果我在状态4,我看到c
那就在这结束了,所以这个确定性有限状态机
能像上面那个一样接受同样的字符串
这两个字符串,abc和ac
都在它里面,但是它没有
epsilon转换或者歧义
在任意特定的节点里,不会有两条标示为a的流出的边界
也不会有epsilon转换
让我们来看看另一个例子
再一次,我将构造一个有限状态机
在这个有限状态机里的每一个状态
都对应于非确定性有限状态机的
一组状态
再次说明下,已知一个非确定性的状态及
我将构建一个能够接受同样语言的确定性有限状态机
而我实现的方法似乎
在d里每一个状态将对应于
非确定性状态机里的一组状态