In this problem, we have a bit of a challenge, and I've accordingly labeled it with
2 gold stars, but what we want to do here,
is optimize a finite state machine.
So to go through an example, let's say we have this finite state machine.
There's 1 accepting state at state 1, and then we have these few others.
If you quickly look at it and think about what's going on,
once you take a path down the b to state 2,
you can never get to the accepting state.
From state 2, 3, or 4, there's no way to get to state 1.
So any string that goes down this path is always going to fail.
This state machine is equivalent to the one that doesn't include any of these states.
So we can make it a lot simpler.
Why would we want to do this?
Well, if you haven't noticed we've been using a lot of regular expressions
in building our web browser.
Those regular expressions are represented as finite state machines,
and that's how they're processed.
In order to make our web browser faster, it turns out we want as small finite state machines
as possible.
So what we're going to do is write code.
Given a definition of finite state machine like the that we have here,
we're going to identify states that don't matter towards the execution,
and we call those dead states and remove them from the definition,
while maintaining the exact same language, while recognizing the exact same strings
that our finite state machine did before.
So how are we going to this? Let's come up with a plan.
So here we have "The Plan."
Step 1--Let's find the live states and the dead states.
We're going to do this by just finding the live states and assuming everything else is dead.
So how are we going to do that?
Well, we're going to find all the states, and we can do that by iterating through our dictionary,
and with each state, we're going to run nfsmaccepts,
which is from homework 1, and it's a procedure that given a definition
for a finite state machine, a starting state, and the accepting states,
it sees if it's possible to get from that state to any accepting state--
if it's possible to succeed from where we're at.
So if I give this definition in state 3, it's going to tell me, no, we can't get to state 1
or any accepting state for that matter.
If I give a 1, it's going to say, yep, this is all good.
So that's actually going to be your definition for live versus dead.
It can actually find a live state versus a dead state, which is awesome.
Step 2--We're going to create a new finite state machine that doesn't have any
of the dead states.
In order to make it a really good, kind of clean, definition, we have to take some care.
We don't want to include any transitions that lead to dead states.
We want to remove all of the dead states,
and we also want to remove states that no longer point to any live states.
So here I have a bunch of little subparts.
We're going to go through each edge state, each entry in our dictionary.
If the current state is dead, we're not going to copy it into our new finite state machine.
Otherwise, we're going to go through all of the destinations it had in the original
finite state machine and prepare to copy over any that are still alive.
If there are none that are still alive, we're going to remove that edge completely.
We're not going to copy it into a new one.
Once we have repeated that process in every state edge thing in the graph,
we're going to update our accepting state list accordingly.
We don't want to have any accepting states that are dead.
So let's go to the solution.
One of the first things I did is I copied in nondeterministic finite state machine accepts
directly from unit 1 homework.
It hasn't changed a bit.
Now I'm going to do my trimming of my finite state machine.
So like I said in my outline, I'm going to find all the states,
just so I have a record of them, and it doesn't really matter if I have duplicates.
It might slow down the trimming a bit, but I'm doing this to save time
when I'm running the execution, not for the trimming so much.
For each state, if it's live, I can tell by running nfsmaccepts,
and if it is live, I'm going to add it to a list of live states.
Now I'm going to create a new dictionary of edges--my new representation,
and go through all of the old ones to see if they're still live and update them accordingly.
So for each edge in the old dictionary, if that state is live,
then I'm going to calculate the new destinations, meaning I'm going to remove the destinations
that are now dead.
So if that destination is live, I'm going to append it to the list.
But I only want to set this new edge to my new finite state machine dictionary
if the destinations are not empty.
There's really no point in having an edge that goes to nowhere,
that goes to fail.
We just kind of always assume that if the edge doesn't exist, then we're going to fail.
Lastly, I want to update my accepting states to only those that are live.
I'm going to return the tuple of the new edges and the new accepting states.
And that's it.
Look! It's true! So much true!
True means good. It means meaning and greatness.
この問題は少し難しいので 2つ星レベルに分類します
ここでは有限状態機械を最適化していきます
図のような有限状態機械があったとします
ステート1には受理状態が1つあり 他にもいくつかステートがあります
図をよく見て考えてください
bの道を通ってステート2に進めば 受理状態には行けません
ステート2、ステート3またはステート4から ステート1に行く道はなく
この道を行く文字列はどれも失敗に終わります
この状態機械はステート1以外を 含まないのと同じです
ならばもっとシンプルにしましょう
でも何のためにですか？
Webブラウザを作るために 多くの正規表現を使ってきました
正規表現は有限状態機械として表され そして処理されます
つまりブラウザの高速化に 有限状態機械の小型化は必須なのです
ではコードを書いていきます
この有限状態機械の定義を基に考えましょう
まず実行に関係しないステートを識別し
それらを死状態として定義から取り除きます
ただし最適化前に使われていた言語をそのまま保ち
まったく同じ文字列と一致するようにしたまま 取り除く必要があります
どのように進めるか計画を立てましょう
これが計画です
ステップ1では生状態と死状態を探します
生状態を探しそれ以外は死んでいると推測します
具体的な方法はこうです
まずは辞書を反復しすべてのステートを探します
そしてそれぞれのステートに nfsmacceptsを実行します
これはレッスン1の宿題に出てきました
有限状態機械の定義として
開始ステートと受理状態 そして遷移の辞書を受け取り
あるステートから受理状態に たどりつけるかどうかを見るプロシージャでした
nfsmacceptsに図の定義とステート3を与えると
ステート1には行けず つまりどの受理状態にも行けません
ステート1を与えると成功します
これを生と死の定義として
生状態と死状態を見分けていきます 楽しいですね
ステップ2では死状態を持たない 新しい有限状態機械を作ります
賢くきれいな定義を作るために 注意すべきことがあります
死状態につながる遷移は含めません
すべての死状態を取り除き
生状態へとつながらないステートも 取り除いていきます
詳細を確認しましょう
各エッジのステートと辞書のエントリを見ます
今のステートが死状態なら 新しい有限状態機械にコピーしません
そうでなければ元の有限状態機械にあった すべての行き先を見て
生状態のものをすべてコピーする準備をします
生状態がない場合は そのエッジを取り除きコピーはしません
図にあるすべてのステートで そのプロセスを繰り返したら
それに基づき受理状態のリストを更新します
死んでいる受理状態は必要ありません
解答を見てみましょう
まずレッスン1の宿題からnfsmacceptsのコードを
そっくりそのままコピーしました 何も変えていません
次は有限状態機械のトリミングです
先ほど説明したようにすべてのステートを探します
コピーが存在することもあります
少しトリミングに時間がかかるかもしれませんが
実行にかかる時間が節約できれば問題ありません
各ステートが生きているかどうかは nfsmacceptsを実行すれば分かります
もし生きていたら生状態のリストに加えます
では新しいエッジの辞書を作成しましょう
もし古い辞書のエッジの遷移元に生状態があれば
それを基に更新していきます
新しい行き先を計算し 死んでいる行き先を取り除くわけです
古いエッジの行き先が生きていたら リストに追加します
しかし新しい有限状態機械に 新しいエッジを設定するのは
行き先が空でない場合のみです
どこにも行き着かず失敗するエッジはいりません
エッジが存在しない場合は失敗すると推測します
最後に受理状態を生きているものだけとする 更新を加えてください
そして新しいエッジと新しい受理状態の タプルを返します
これで完了です
見てください Trueと出ています
Trueは真です
いいですね すばらしいです
Neste problema, temos um desafio, e por isso eu o marquei
com duas estrelas. O que queremos fazer aqui
é otimizar um atômato de estados finito.
Vejamos um exemplo. Suponha que temos este autômato de estados finito.
Ele tem um estado de aceitação -- estado 1 -- e temos estes outros estados.
Se você olhar rapidamente e pensar um pouco,
verá que uma vez que tomamos o caminho com 'b' para o estado 2,
nunca podemos chegar a um estado de aceitação.
Do estado 2, 3, ou 4, não há como chegar ao estado 1.
Portanto, qualquer string que leve a este camoinho sempre irá falhar.
Este autômato é equivalente a este outro, que não inclui estes estados.
Portanto, podemos tornálo muito mais simples.
Porque desejamos fazer isso?
Bem, se você ainda não notou, temos usado muito expressões regulares,
para construir nosso web browser.
Essas expressões regulares são representadas como autômatos de estados finitos,
e é assim que são processadas.
Para tornar nosso web browser mais rápido, queremos autômatos de estados finitos tão simples
quanto possível.
Então, vamos escrever um código para,
dada uma definição de um autômato de estados finito, tal como este aqui,
identificar estado que não são releventes para a execução,
que vamos chamar de estados mortos, e removê-los da definição,
mantendo exatamente a mesma linguagem - reconhecendo exatamente os mesmo strings. --
que o nosso autômato de estados finito original.
Como vamos fazer isso? Vamos traçar um plano.
Aqui está 'O Plano'.
Passo 1: vamos encontrar os estado vivos e os estados mortos.
Vamos fazer isso simplesmente encontrando os estados vivos e supondo que todos os demais são mortos.
Como vamos então fazer isso?
Bem, vamos encontrar todos os estados, e podemos fazer isso iterando sobre o nosso dicionário,
Para cada estado, vamos executar nfsmaccepts --
que codificamos no exercício 1 e que é uma função que, dada uma definição
de um atômato finito, um estado inicial, e os estado de aceitação,
verifica se é possível chegar desse estado até um estado de aceitação --
se é possível ter sucesso a partir de onde estamos.
Portnto, se eu dou esta definição e o estado 3, a função vai retornar que não, não posso chegar ao estado 1,
ou a qualquer outro estado de aceitação.
Se eu dou como entrada 1, a função retorna sim, ok.
Então, esta será nossa definição de vivo versus morto.
Eu realmente posso dizer se um estado é vivo ou morto -- isso é ótimo!
Passo 2: Criar um novo autômato finito, que não tenha
nenhum estado morto.
Para obter uma definição realmente boa, bem limpa, é necessário ter um certo cuidado.
Não queremos incluir transições que levem a um estado morto.
Queremos remover todos os estados mortos,
e também queremos remover estado que não apontam mais para nenhum estado vivo.
Então, aqui, temos algumas pequenas subpartes.
Vamos percorrer cada arco do grafo -- cada entrada do dicionário.
Se o estado de origem for morto, não vamos copiá-lo no nosso novo autômato.
Caso contrário, vamos percorrer cada um dos estados de destino,
no nosso autômato original, e nos preparar para copiar todos aqueles que ainda permanecem vivos.
Se não existir nenhum ainda vivo, vamos remover o arco completamente --
não vamos copiá-lo para o autômato novo.
Uma vez que tenhamos repetido esse processo para cada arco do grafo,
vamos atualizar nossa lista de estados de acitação, de maneira correspondente:
Não queremos nenhum estado de aceitação que seja morto.
Vamos então à solução.
A primeira coisa que eu fiz foi copiar nsfmaccepts,
diretamente do exercício da unidade 1,
sem modificar nada.
Agora vou simplificar meu autômato de estados finito.
Como eu disse antes, vou ter que encontrar todos os estados,
de modo que eu tenha uma lista com todos eles, e não importa se eles ocorrem duplicados na lista.
Isso pode tornar minha simplificação um pouco mais lenta, mas eu estou fazendo assim para ecomizar tempo
na execução, mesmo que não na simplificação.
Para cada estado, se ele for vivo -- eu posso determinar isso usando nfsmaccepts --
se ele for vivo vou adicioná-lo à lista de estados vivos.
Agora vou criar um novo dicionário de arcos -- minha nova representação --
e vou percorrer todos os arcos antigos, para ver se eles envolvem apenas estados vivos, e atualizá-lo de modo apropriado.
Então, para cada arco do dicionário, se o estado de origem é vivo,
vou calcular a nova lista de estados de destino, o que significa que vou remover os destinos
que agora estão mortos --
então, se o destino é vivo, vou inclui-lo na lista.
Mas eu apenas quero incluir este arco no dicionário do meu novo autômato finito
se a lista de destinos for não vazia --
não faz sentido incluir um arco que não vai para lugar nenhum,
pois isso significa falha.
É como se supusermos sempre que, se um arco não existe, então temos uma falha.
Finalmente, quero atualizar minha lista de estados de aceitação, de modo que inclua apenas estados vivos.
Vou retornar a tupla com os novos arcos e os novos estados de aceitação.
E é isso.
Veja! É True! É mesmo True!
True significa correto. Significa ótimo.