It turns out that Python's regular expression module
actually uses something very similar to FSM sim under the hood.
You just take the regular expression,
turn it into a finite-state machine, which you've done forwards and backwards
many times, and then check with a simple recursive procedure
to see if the finite-state machine accepts a string.
However, our simulation did not handle epsilon transitions or ambiguity,
and what I mean by ambiguity is what if there are 2 outgoing edges labeled a?
Let's say one of them leads to an accepting state, and one of them doesn't.
What should we do?
Well, there is a formal definition for this kind of ambiguity.
However, it's not going to solve our problems.
We see that a finite-state machine accepts a string s
if there exists even one path from the start state
to any accepting state that follows s.
This finite-state machine accepts a
because there's one way to do it where a causes you
to end up in an accepting state.
If you like, you can say that finite-state machines are generous.
If there's any way to accept, we will make that work.
However, our finite-state machine simulation
didn't code that up, so we're going to have to return
to both of these issues.
Scopriamo che il modulo Python per le espressioni regolari
usa un meccanismo abbastanza simile al nostro simulatore.
Prende l'espressione regolare,
la trasforma in una macchina a stati finiti, come avete avuto modo provare in entrambi i sensi
più volte, e poi la controlla con una semplice procedura ricorsiva
per vedere se la macchina accetta la stringa.
Purtroppo, il nostro simulatore non supporta transizioni epsilon o ambiguità,
cosa succede se ci sono due vertici uscenti entrambi etichettati con 'a' ?
Diciamo che uno conduca ad uno stato accettante, e l'altro no.
Cosa dovremmo fare?
Bhé, c'è una definizione formale per questo tipo di ambiguità.
Che non risolverà il nostro problema però.
Vediamo come una macchina a stati finiti accetta una stringa 's'
se esiste almeno un percorso dallo stato iniziale
ad un qualsiasi stato accettante che segue 's' .
Questa macchina accetta 'a'
poiché c'è un percorso per farlo che
conduce ad uno stato accettante.
Se preferite, potete dire che le macchine a stati finiti sono generose.
Se c'è anche una sola via per accettare, la utilizzeremo.
Purtroppo, la nostra simulazione di macchina a stati finiti
non gestisce questa situazione, quindi dovremo tornarci
per risolvere entrambi questi problemi.
Pythonの正規表現モジュールは
fsmsimと似ているものを使っています
何度もお見せしていますが
正規表現を有限状態機械に変換します
再帰的な手続きで有限状態機械が 文字列を受理するかを
確認することができます
しかしシミュレータはイプシロン遷移と あいまいさは処理しません
あいまいさの例を出します aという2つのエッジのうち
受理ステートに行けるのは1つだけです
どうするべきでしょう？
この例には正式な定義がありますが
それでは問題解決しません
有限状態機械が文字列sを受理するには
開始ステートから受理ステートへとつながる道が
1つでもあれば文字列は受理されます
これなら受理ステートへ
行き着くことができるので
aは受理されます
有限状態機械は寛容だと言えるかもしれません
受理できる遷移が1つでもあればそれでいいのです
しかしfsmsimではこれらを
コーディングしていませんので
この2つの問題を解決する必要があります
O módulo de expressões regulares de Python
usa, de fato, algo bastante similar ao fsmsim, internamente.
Ele pega uma expressão regular
e a transforma esta em um FSM -- esta transformação você fez, num sentido e no outro,
muitas vezes -- e então ele verifica, com um procedimento recursivo simples,
se o FSM aceita o string.
Entretanto, nossa simulação não trata transições epsilon, ou ambiguidade.
O que eu quero dizer com ambiguidade é: o que acontece se existem 2 arcos saindo do estado, com rótulo `a' ?
Digamos que um deles leva a um estado de aceitação, e o outro não.
O que devemos fazer?
Bem, existe uma definição formal para esse tipo de ambiguidade.
Entretanto, isso não vai resolver nossos problemas.
A idéia é que um FSM aceita um string s,
se existe pelo menos um caminho, do estado inicial
a algum estado de aceitação, rotulado com s.
Este FSM aceita `a'
porque existe um caminho para isso, onde `a' nos leva
até um estado de aceitação.
Se você quiser, pode dizer que FSMs são generosas:
se existe uma maneira de aceitar, então aceitamos.
Entretanto, nosso similador de FSM
não codifica esta idéia. Então, vamos ter que retornar
a estas questões.
实际上，Python的正则表达式模块
在内部的操作跟FSM是很相似的
你只要把正则表达式
转换成有限状态机，这个你前前后后已经做了很多次咯
然后用一个简单的递归函数来检查
该有限状态机是否能接受一个字符串
可是，我们的模拟器处理不了epsilon 过渡或者歧义
我这里说的歧义，指的是如果有两条标示为a的边界，怎么办呢？
假设一条指向一个接受状态，另一条不是
我们应该怎么做呢？
对于这种类型的歧义，有一个正式的定义
可是，它不能解决我们的问题
我们看到一个有限状态机能接受一个字符串
如果沿着字符串s，有一条路线能从开始状态
移到任意的接受状态
这个有限状态机能接受a
因为a能在
接受状态结束
如果你喜欢，你可以说有限状态机是"大方"的
如果有任意的方法能接受，它都能起作用
可是，我们的有限状态机模拟器
不能完全实现这点，所以我们必须要回到
所有的这些问题上