Algoritmo de McNaughton e Yamada
Na ciência da computação teórica , e em particular na teoria dos autômatos finitos , o algoritmo de McNaughton e Yamada é um algoritmo para calcular uma expressão regular a partir de um autômato finito. Seu nome é uma homenagem a Robert McNaughton e Hisao Yamada , dois cientistas americanos e japoneses que descreveram o algoritmo. Esse algoritmo também é chamado de algoritmo de Kleene.
Outro algoritmo, apresentado no mesmo artigo, que possibilita a construção de um autômato sem transições épsilon de uma expressão regular também é denominado algoritmo de McNaughton e Yamada .
Princípio
Dado um autômato com n estados, e cujos estados são numerados de 1 a n , damos uma expressão para linguagens compostas pelas palavras que rotulam os caminhos de i a j , para qualquer par i , j . Essa expressão é construída por indução usando uma condição nos caminhos; esta condição estipula que os caminhos passam apenas por determinados estados autorizados. A cada iteração do algoritmo, fixamos um novo estado pelo qual nos permitimos passar. No final do algoritmo, obtemos todos os caminhos possíveis.
O funcionamento deste algoritmo, então, recupera o algoritmo Floyd-Warshall em grafos, onde a cada novo passo, nos permitimos passar por um novo vértice fixo.
Descrição
Seja um autômato finito em um alfabeto , dado por um conjunto finito de estados , um conjunto de transições e conjuntos de estados iniciais respectivamente terminais.
NO=(Q,F,eu,T){\ displaystyle {\ mathcal {A}} = (Q, {\ mathcal {F}}, I, T)}
NO{\ displaystyle A}
Q{\ displaystyle Q}
F⊂Q×NO×Q{\ displaystyle {\ mathcal {F}} \ subconjunto Q \ times A \ times Q}
eu,T⊆Q{\ displaystyle I, T \ subseteq Q}![{\ displaystyle I, T \ subseteq Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa14c049b9a16cd322f4f2887c245c307906a6f2)
Denotamos o conjunto de palavras que são rótulos de caminho de para . A linguagem reconhecida pelo autômato é o conjunto
eup,q{\ displaystyle L_ {p, q}}
p{\ displaystyle p}
q{\ displaystyle q}
eu{\ displaystyle L}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
eu=⋃eu∈eu⋃t∈Teueu,t{\ displaystyle L = \ bigcup _ {i \ in I} \ bigcup _ {t \ in T} L_ {i, t}}![{\ displaystyle L = \ bigcup _ {i \ in I} \ bigcup _ {t \ in T} L_ {i, t}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1387dfb65308195b65e4948e57ce9c879337e9a0)
O algoritmo de McNaugthon e Yamada é um método para calcular expressões regulares para .
eup,q{\ displaystyle L_ {p, q}}![{\ displaystyle L_ {p, q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13ee88eca14677535fa3d143ece9ea61eb8abc2f)
Denotamos a expressão para o conjunto de palavras que rotulam caminhos de para e cujos vértices intermediários são menores ou iguais a . Os vértices inicial e final não são intermediários, portanto, não são restritos a serem menores ou iguais a .
eup,q(k){\ displaystyle L_ {p, q} ^ {(k)}}
p{\ displaystyle p}
q{\ displaystyle q}
k{\ displaystyle k}
p{\ displaystyle p}
q{\ displaystyle q}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Nós os construímos por indução , começando e terminando com . Quando , a restrição em não é mais uma restrição, e se , e .
eup,q(k){\ displaystyle L_ {p, q} ^ {(k)}}
k{\ displaystyle k}
k=0{\ displaystyle k = 0}
k=não{\ displaystyle k = n}
k=não{\ displaystyle k = n}
k{\ displaystyle k}
eup,q(não)=eup,q{\ displaystyle L_ {p, q} ^ {(n)} = L_ {p, q}}
p≠q{\ displaystyle p \ neq q}
ε+eup,p(não)=eup,p{\ displaystyle \ varepsilon + L_ {p, p} ^ {(n)} = L_ {p, p}}![{\ displaystyle \ varepsilon + L_ {p, p} ^ {(n)} = L_ {p, p}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a91cf4d450dac3a31782d4b237413fcf55ec7f97)
Pois , como os vértices são numerados a partir de 1, a restrição simplesmente expressa que não há vértices intermediários. Os únicos caminhos são transições de para (ignoramos um caminho de comprimento 0 em um estado ).
k=0{\ displaystyle k = 0}
p{\ displaystyle p}
q{\ displaystyle q}
p{\ displaystyle p}![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
Então nós temos
eup,q(0)=∑(p,no,q)∈Fno{\ displaystyle L_ {p, q} ^ {(0)} = \ sum _ {(p, a, q) \ in {\ mathcal {F}}} a}![{\ displaystyle L_ {p, q} ^ {(0)} = \ sum _ {(p, a, q) \ in {\ mathcal {F}}} a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b89d0d4c968ff2deb091b49be700cf6d5852976)
Para recorrência, consideramos um caminho de para cujos vértices intermediários são menores que . Dois casos são então possíveis:
p{\ displaystyle p}
q{\ displaystyle q}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
- os vértices intermediários são menores que ; então o rótulo está em ;k-1{\ displaystyle k-1}
eup,q(k-1){\ displaystyle L_ {p, q} ^ {(k-1)}}![{\ displaystyle L_ {p, q} ^ {(k-1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d76bbb105d0524f80e5041f4e2ab99aed7e0a218)
- o caminho passa pelo estado . Em seguida, decompomos o caminho em partes cujos vértices intermediários são menores que . Para isso, consideramos cada ocorrência do vértice neste caminho: entre duas ocorrências consecutivas, os vértices intermediários são menores que k-1. Então temos a fórmulak{\ displaystyle k}
k-1{\ displaystyle k-1}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
eup,q(k)=eup,q(k-1)+eup,k(k-1)(euk,k(k-1))∗euk,q(k-1){\ displaystyle L_ {p, q} ^ {(k)} = L_ {p, q} ^ {(k-1)} + L_ {p, k} ^ {(k-1)} (L_ {k, k} ^ {(k-1)}) ^ {*} L_ {k, q} ^ {(k-1)}}![{\ displaystyle L_ {p, q} ^ {(k)} = L_ {p, q} ^ {(k-1)} + L_ {p, k} ^ {(k-1)} (L_ {k, k} ^ {(k-1)}) ^ {*} L_ {k, q} ^ {(k-1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1471e8648f81474edb75e71b8dee50ca1ef7ab6a)
.
Portanto, existem etapas ( ). Cada uma das etapas requer o cálculo de expressões, e o tamanho das próprias expressões aumenta com isso . Se for facilmente programável, o algoritmo é bastante doloroso para as mãos. Então, é útil usar as regras que permitem simplificar as expressões regulares.
não+1{\ displaystyle n + 1}
k=0,...,não{\ displaystyle k = 0, \ ldots, n}
não2{\ displaystyle n ^ {2}}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Pseudo-código
Iremos representá-los (respectivamente ) na forma de matrizes, cujo coeficiente é (respectivamente ). Temos então, para um autômato de estado finito no alfabeto :
eu(k){\ displaystyle L ^ {(k)}}
eu{\ displaystyle L}
(eu,j){\ displaystyle (i, j)}
eueu,j(k){\ displaystyle L_ {i, j} ^ {(k)}}
eueu,j{\ displaystyle L_ {i, j}}
NO=(Q,F,eu,T){\ displaystyle {\ mathcal {A}} = (Q, {\ mathcal {F}}, I, T)}
não{\ displaystyle n}
NO{\ displaystyle A}![NO](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Fonction McNaughton-Yamada(
A{\displaystyle {\mathcal {A}}}![{\mathcal {A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/280ae03440942ab348c2ca9b8db6b56ffa9618f8)
)
L:=(∑(p,a,q)∈Fa)1≤p,q≤n{\displaystyle L:=(\sum _{(p,a,q)\in {\mathcal {F}}}a)_{1\leq {\mathit {p}},{\mathit {q}}\leq n}}![{\displaystyle L:=(\sum _{(p,a,q)\in {\mathcal {F}}}a)_{1\leq {\mathit {p}},{\mathit {q}}\leq n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0e38d584501b2ddc5a46e2609b3dfccff8f0e9c)
\\à l'itération k de la boucle for, cette matrice représente
L(k){\displaystyle L^{(k)}}![{\displaystyle L^{(k)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5388a4b0101c5d0c462488fa5541cabbfb20180)
for
k:=1{\displaystyle {\mathit {k}}:=1}![{\mathit {k}}:=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a1dc6c08ea9913bb9b1911329adc1277396d1a8)
to
n{\displaystyle {\mathit {n}}}![{\mathit {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8379ab758c42519867fc601fa155ea3175a05b3)
for
p:=1{\displaystyle {\mathit {p}}:=1}![{\displaystyle {\mathit {p}}:=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e3f7a53ef4bfb34a9348714175a25413a3ac1c5)
to
n{\displaystyle {\mathit {n}}}![{\mathit {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8379ab758c42519867fc601fa155ea3175a05b3)
for
q:=1{\displaystyle {\mathit {q}}:=1}![{\displaystyle {\mathit {q}}:=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3be530893b68460e76bbda646a5858abb1330541)
to
n{\displaystyle {\mathit {n}}}
Lp,q:=Lp,q+Lp,k(Lk,k)∗Lk,q{\displaystyle L_{{\mathit {p}},{\mathit {q}}}:=L_{{\mathit {p}},{\mathit {q}}}+L_{{\mathit {p}},{\mathit {k}}}(L_{{\mathit {k}},{\mathit {k}}})^{*}L_{{\mathit {k}},{\mathit {q}}}}![{\displaystyle L_{{\mathit {p}},{\mathit {q}}}:=L_{{\mathit {p}},{\mathit {q}}}+L_{{\mathit {p}},{\mathit {k}}}(L_{{\mathit {k}},{\mathit {k}}})^{*}L_{{\mathit {k}},{\mathit {q}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b1d740698791e90cd8794e464fface3d7e6440b)
R :=
∅{\displaystyle \emptyset }![\emptyset](https://wikimedia.org/api/rest_v1/media/math/render/svg/6af50205f42bb2ec3c666b7b847d2c7f96e464c7)
\\expression rationnelle à retourner
for
p∈I{\displaystyle {\mathit {p}}\in I}![{\displaystyle {\mathit {p}}\in I}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8aa3f65997c334335e5f7d9b506532ba193bf56b)
:
for
q∈T{\displaystyle {\mathit {q}}\in T}![{\displaystyle {\mathit {q}}\in T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d17a2c8eeae7bd9027f1113dc22083bb9da0b8f8)
:
if
p==q{\displaystyle {\mathit {p}}=={\mathit {q}}}![{\displaystyle {\mathit {p}}=={\mathit {q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c67a15d30ddcf8749c4272fd73569133e7dce58f)
then
R := R +
ε{\displaystyle \varepsilon }![\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
+
Lp,p{\displaystyle L_{p,p}}![{\displaystyle L_{p,p}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0381c5ad43586e6be9530d6edab131d23d64ecd6)
\\on n'ajoute
ε{\displaystyle \varepsilon }![\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
qu'aux
Lp,p{\displaystyle L_{p,p}}![{\displaystyle L_{p,p}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0381c5ad43586e6be9530d6edab131d23d64ecd6)
où
p∈I∩T{\displaystyle {\mathit {p}}\in I\cap T}![{\displaystyle {\mathit {p}}\in I\cap T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d4b976e6734a4c4e484e5bf286abbbf4080ca38)
else
R := R +
Lp,q{\displaystyle L_{p,q}}![{\displaystyle L_{p,q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13ee88eca14677535fa3d143ece9ea61eb8abc2f)
retourner R
Fin Fonction
Exemplos
Um primeiro exemplo
Vamos aplicar o algoritmo de McNaughton e Yamada ao autômato representado. Usaremos a representação de matriz introduzida na parte anterior. Nós temos :
NO1{\ displaystyle {\ mathcal {A}} _ {1}}![{\ displaystyle {\ mathcal {A}} _ {1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97d7d5893bb0561776b2f3806205578a690da032)
-
eu(0)=(nob∅b){\ displaystyle L ^ {(0)} = {\ begin {pmatrix} a & b \\\ emptyset & b \ end {pmatrix}}}
;
-
eu(1)=(no+no(no)∗nob+no(no)∗b∅b+∅(no)∗b)=(no+no∗b∅b){\ displaystyle L ^ {(1)} = {\ begin {pmatrix} a + a (a) ^ {*} a & b + a (a) ^ {*} b \\\ emptyset & b + \ emptyset ( a) ^ {*} b \ end {pmatriz}} = {\ begin {pmatriz} a ^ {+} & a ^ {*} b \\\ conjunto vazio & b \ end {pmatriz}}}
;
-
eu(2)=(no++(no∗b)(b)∗∅no∗b+(no∗b)(b)∗b∅b+bb∗b)=(no+no∗b+∅b+){\ displaystyle L ^ {(2)} = {\ begin {pmatrix} a ^ {+} + (a ^ {*} b) (b) ^ {*} \ emptyset & a ^ {*} b + (a ^ {*} b) (b) ^ {*} b \\\ emptyset & b + bb ^ {*} b \ end {pmatrix}} = {\ begin {pmatrix} a ^ {+} & a ^ {* } b ^ {+} \\\ emptyset & b ^ {+} \ end {pmatriz}}}
.
De onde .
eu=(ϵ+no+no∗b+∅ϵ+b+)=(no∗no∗b+∅b∗){\ displaystyle L = {\ begin {pmatrix} \ epsilon + a ^ {+} & a ^ {*} b ^ {+} \\\ emptyset & \ epsilon + b ^ {+} \ end {pmatrix}} = {\ begin {pmatrix} a ^ {*} & a ^ {*} b ^ {+} \\\ emptyset & b ^ {*} \ end {pmatrix}}}![{\ displaystyle L = {\ begin {pmatrix} \ epsilon + a ^ {+} & a ^ {*} b ^ {+} \\\ emptyset & \ epsilon + b ^ {+} \ end {pmatrix}} = {\ begin {pmatrix} a ^ {*} & a ^ {*} b ^ {+} \\\ emptyset & b ^ {*} \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78cf9522e53a5c9b318b9d66cfd598f83743a91d)
A linguagem reconhecida por é então denotada pela expressão regular . Após simplificações, temos , qual é o resultado esperado.
eu(NO1){\ displaystyle L ({\ mathcal {A}} _ {1})}
NO1{\ displaystyle {\ mathcal {A}} _ {1}}
eu1,1+eu1,2=no∗+no∗b+{\ displaystyle L_ {1,1} + L_ {1,2} = a ^ {*} + a ^ {*} b ^ {+}}
eu(NO1)=no∗b∗{\ displaystyle L ({\ mathcal {A}} _ {1}) = a ^ {*} b ^ {*}}![{\ displaystyle L ({\ mathcal {A}} _ {1}) = a ^ {*} b ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a51ce5f5c977dea7a143690a22a7a061cf5f0335)
Consideremos agora o mesmo autômato, mas com diferentes numerações dos estados. O algoritmo aplicado a este autômato fornece:
- eu(0)=(b∅bno){\ displaystyle L ^ {(0)} = {\ begin {pmatrix} b & \ emptyset \\ b & a \ end {pmatrix}}}
![{\ displaystyle L ^ {(0)} = {\ begin {pmatrix} b & \ emptyset \\ b & a \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/912830cc4219a755288e21c89a339e4bed907247)
- eu(1)=(b+∅bno){\ displaystyle L ^ {(1)} = {\ begin {pmatrix} b ^ {+} & \ emptyset \\ b & a \ end {pmatrix}}}
![{\ displaystyle L ^ {(1)} = {\ begin {pmatrix} b ^ {+} & \ emptyset \\ b & a \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eaa10ab892d7b374ab3ebb225834425b517c17f)
- eu(2)=(b+∅no∗b+no+){\ displaystyle L ^ {(2)} = {\ begin {pmatrix} b ^ {+} & \ emptyset \\ a ^ {*} b ^ {+} & a ^ {+} \ end {pmatrix}}}
![{\ displaystyle L ^ {(2)} = {\ begin {pmatrix} b ^ {+} & \ emptyset \\ a ^ {*} b ^ {+} & a ^ {+} \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58ee4e5fbae18fc1b940335741d93135611eb66f)
De onde .
eu=(b∗∅no∗b+no∗){\ displaystyle L = {\ begin {pmatrix} b ^ {*} & \ emptyset \\ a ^ {*} b ^ {+} & a ^ {*} \ end {pmatrix}}}
eu(NO1){\ displaystyle L ({\ mathcal {A}} _ {1})}
é então denotado por , ou seja, exatamente a mesma expressão regular de antes: para este exemplo particular, a escolha do novo estado autorizado em cada etapa não altera a expressão racional obtida no final do algoritmo.
eu2,2+eu2,1=no∗+no∗b+{\ displaystyle L_ {2,2} + L_ {2,1} = a ^ {*} + a ^ {*} b ^ {+}}![{\ displaystyle L_ {2,2} + L_ {2,1} = a ^ {*} + a ^ {*} b ^ {+}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d519e24fc474f6dc49eee4b380134c9485533a47)
Um segundo exemplo, onde a numeração dos estados altera o resultado
Vamos agora dar o exemplo apresentado na obra de referência de Sakarovitch. Agora vamos aplicar o algoritmo ao autômato . Nós temos :
NO2{\ displaystyle {\ mathcal {A}} _ {2}}![{\ displaystyle {\ mathcal {A}} _ {2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68792123d9a3278616d5751c2b2bb05981ff0039)
- eu(0)=(nobnob){\ displaystyle L ^ {(0)} = {\ begin {pmatrix} a & b \\ a & b \ end {pmatrix}}}
![{\ displaystyle L ^ {(0)} = {\ begin {pmatrix} a & b \\ a & b \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fa0c3154a932765dfc60fad10bc552c1ef0bf98)
- eu(1)=(no+no∗bno+no∗b){\ displaystyle L ^ {(1)} = {\ begin {pmatrix} a ^ {+} & a ^ {*} b \\ a ^ {+} & a ^ {*} b \ end {pmatrix}}}
![{\ displaystyle L ^ {(1)} = {\ begin {pmatrix} a ^ {+} & a ^ {*} b \\ a ^ {+} & a ^ {*} b \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b5bd4595473a74869da65ed6f25966cc257d5ee)
- eu(2)=((no∗b)∗no+(no∗b)+(no∗b)∗no+(no∗b)+){\ displaystyle L ^ {(2)} = {\ begin {pmatrix} (a ^ {*} b) ^ {*} a ^ {+} & (a ^ {*} b) ^ {+} \\ ( a ^ {*} b) ^ {*} a ^ {+} & (a ^ {*} b) ^ {+} \ end {pmatrix}}}
![{\ displaystyle L ^ {(2)} = {\ begin {pmatrix} (a ^ {*} b) ^ {*} a ^ {+} & (a ^ {*} b) ^ {+} \\ ( a ^ {*} b) ^ {*} a ^ {+} & (a ^ {*} b) ^ {+} \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de6e9983ccd8e4390bc5a379451711d0f7548866)
-
eu=(ε+(no∗b)∗no+(no∗b)+(no∗b)∗no+(no∗b)∗){\ displaystyle L = {\ begin {pmatrix} \ varepsilon + (a ^ {*} b) ^ {*} a ^ {+} & (a ^ {*} b) ^ {+} \\ (a ^ { *} b) ^ {*} a ^ {+} & (a ^ {*} b) ^ {*} \ end {pmatrix}}}
.
De onde .
eu(NO2)=eu1,1=ε+(no∗b)∗no+{\ displaystyle L ({\ mathcal {A}} _ {2}) = L_ {1,1} = \ varepsilon + (a ^ {*} b) ^ {*} a ^ {+}}![{\ displaystyle L ({\ mathcal {A}} _ {2}) = L_ {1,1} = \ varepsilon + (a ^ {*} b) ^ {*} a ^ {+}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77a66c2b7613e95d135091e6c267966a7c254fd1)
Quanto ao primeiro exemplo, vamos aplicar o algoritmo novamente, alterando a numeração dos estados. Nós temos :
- eu(0)=(bnobno){\ displaystyle L ^ {(0)} = {\ begin {pmatrix} b & a \\ b & a \ end {pmatrix}}}
![{\ displaystyle L ^ {(0)} = {\ begin {pmatrix} b & a \\ b & a \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfdfcde7dd5c85b9496f396cc9209495f7e5be3f)
- eu(1)=(b+b∗nob+b∗no){\ displaystyle L ^ {(1)} = {\ begin {pmatrix} b ^ {+} & b ^ {*} a \\ b ^ {+} & b ^ {*} a \ end {pmatrix}}}
![{\ displaystyle L ^ {(1)} = {\ begin {pmatrix} b ^ {+} & b ^ {*} a \\ b ^ {+} & b ^ {*} a \ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c8df3b9b00a85a8097dfe326e1c1c64cc95468d)
- eu(2)=((b∗no)∗b+(b∗no)+(b∗no)∗b+(b∗no)+){\ displaystyle L ^ {(2)} = {\ begin {pmatrix} (b ^ {*} a) ^ {*} b ^ {+} & (b ^ {*} a) ^ {+} \\ ( b ^ {*} a) ^ {*} b ^ {+} & (b ^ {*} a) ^ {+} \ end {pmatriz}}}
![{\ displaystyle L ^ {(2)} = {\ begin {pmatrix} (b ^ {*} a) ^ {*} b ^ {+} & (b ^ {*} a) ^ {+} \\ ( b ^ {*} a) ^ {*} b ^ {+} & (b ^ {*} a) ^ {+} \ end {pmatriz}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/418eaa6cf1530a553f690b5f21a709d5868192c9)
-
eu=((b∗no)∗b∗(b∗no)+(b∗no)∗b+(b∗no)∗){\ displaystyle L = {\ begin {pmatrix} (b ^ {*} a) ^ {*} b ^ {*} & (b ^ {*} a) ^ {+} \\ (b ^ {*} a ) ^ {*} b ^ {+} & (b ^ {*} a) ^ {*} \ end {pmatriz}}}
.
Daí : a expressão racional obtida para a mesma língua é diferente.
eu(NO2)=eu2,2=(b∗no)∗{\ displaystyle L ({\ mathcal {A}} _ {2}) = L_ {2,2} = (b ^ {*} a) ^ {*}}![{\ displaystyle L ({\ mathcal {A}} _ {2}) = L_ {2,2} = (b ^ {*} a) ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c5b85b45d8dff40467cdbbfe61af34e65fc81aa)
Notas e referências
-
McNaughton e Yamada 1960 .
-
(em) Jacques Sakarovitch, Elementos da teoria dos autômatos , Cambridge, Cambridge University Press,1 ° de outubro de 2009, 782 p. ( ISBN 978-0-521-84425-3 , aviso BnF n o FRBNF42078268 ) , p.96
Bibliografia
-
(pt) Robert McNaughton e Hisao Yamada, “ Expressões regulares e gráficos de estado para autômatos ” , IRE Trans. Electronic Computers , vol. CE-9, n o 1,Janeiro de 1960, p. 39-47 ( DOI 10.1109 / TEC.1960.5221603 ).
-
(pt) John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Introdução à Teoria dos Autômatos, Linguagens e Computação , Pearson Addison Wesley,2007, 3 e ed. , xvii + 535 pág. ( ISBN 978-0-321-45536-9 e 0201441241 ) - Seção 3.2.1 De DFAs para expressões regulares , p. 93-98 .
-
(pt) Jacques Sakarovitch, Elementos da teoria dos autômatos, Cambridge University Press,1 ° de outubro de 2009, 782 p. ( ISBN 978-0521844253 ) , p. 96
Artigos relacionados
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">