Well, let's try to reason these out since they're extra complicated.
Suppose you give me your finite state machine A.
Here I've drawn all these dots to mean it could be bigger in the middle.
I don't get to know what it is. This is going to have to work for any finite state machine.
But I do know that it has a start state and an end state--a final state.
Here's what I'm going to do. I'm going to draw another copy of A on my paper.
Then I'm going to go back to the first one and where it was a final state,
I'm going to make it not a final state, so I change this part.
Then I'm going to add an epsilon transition here, and I'm going to erase this other start state arrow.
Now I have a new finite state machine that accepts strings of the following form--
there has to be some part x here that would've been accepted by A.
Then there's some possibly different part y here that would be accepted by A again,
so in general I accept x epsilon y or just xy.
In fact, I can always do this.
If you give me any finite state machine, I can always make a twice as big finite state machine
that accepts one string from you followed by one independent, separate string from you.
However, for this one it's going to be a little more complicated.
It turns out that the answer is only sometimes.
Let me give you an example for yes and an example for no.
Let's say the finite state machine you give me for big B just has one string in it--lowercase b.
I'll do the same trickery as before, and now I have a new finite state machine that accepts bb.
Since there is only one string in the language, I've now doubled it. This works fine.
I can do it at least once, but now here comes the evil part.
This upper example--this blue example--of B totally worked.
Now I'm going give you an example for B that does not.
Here, B is a*x.
This finite state machine accepts the regular expression a*x.
Any number of a's, possibly zero, but then you need an x.
Now, note the difference between this sentence and its earlier copy.
This requires exactly the same string double.
Let's imagine that I do complete this finite state machine construction--
the same sort of thing I've done before.
Now I'm going to write out some of the strings that would be in a*x twice.
Well, I could have no a's, so then I have no a's followed by an x.
Or I could have one a--that's looking okay so far.
Or I could have two a's, or I could have three a's.
This pattern should be looking ominous.
Or in general, if I were able to double this machine so that it accepted the same string both times
rather than a new string each time, I would be recognizing (a^n)x(a^n)x.
For the same reason that a^Nb^n can't be recognized--it's not regular--neither can this.
Here we have one positive example and one negative example,
so it only holds sometimes.
This was super tricky. Do not feel bad if you didn't see this the first time.
複雑なのでそれぞれ考えてみます
有限状態機械Aを与えたとします
点線部分は省略を表します
それが何であれ その有限状態機械について
言えなければなりません
少なくとも開始ステートと受理ステートがあります
まず有限状態機械をコピーします
そして最後のステートを
受理ステートではないように変更します
イプシロン遷移を加えて
右の開始ステートを消します
新しい有限状態機械は
Aでxを受理した部分に相当します
右側はAの部分でyを受理します
全体ではx、イプシロン、y
つまりxyを受理します
常に成立します
どのような有限状態機械が与えられても
常にその2倍の大きさの有限状態機械を作り
与えられた機械で受理されるある文字列を
つなげたものを受理することができます
次はもう少し複雑です
ときどき成立するが答えです
成立する例としない例を出します
与えられた有限状態機械Bが1つの文字列
小文字のbだけを受理したとします
前と同じように考えて
bbを受理する有限状態機械が作れます
これが言語に含まれる唯一の文字列で
うまく2倍にしました
次は成立しない場合を説明します
上の青い例のBではうまくいきました
そうでないBの例を挙げます
今度のBはa*xです
正規表現でのa*xを受理します
0個以上のaがいくつでも続いたあと
xが必要です
前の文とは違うところがあります
こちらは完全に一致した同じ文字列を
2回繰り返す必要があります
前の操作と同様の操作で
この文のとおりの有限状態機械ができたとします
a*xが2回出てくる文字列の例を見ましょう
aがなくてxxとなることがあります
aが1つでaxaxが来る場合もよさそうです
aが2個や3個でもよいでしょう
どうもこのパターンはよくない気がします
同じ文字列を2回繰り返したものが
受理できるのであれば
これはa^Nx a^Nxを受理することになります
しかし正規表現では
a^N b^Nが受理できないようには表せません
真の例と偽の例を挙げられたので
ときどき成立すると言えます
複雑な問題だったので一見して
分からなかったとしても落ち込まないでください
Bem, vamos tentar raciocinar sobre isso, já que é um pouco complicado.
Suponha que você me dá seu autômato de estados finitos A.
Eu desenhei aqui estes ... para indiar que ele poderia ser maior, com outros estados no meio --
eu não sei o que é isso, isso pode representar qualquer autômato de estados finito.
Mas eu sei que ele tem um estado inicial e um estado final.
Aqui, o que eu vou fazer é: eu vou desenhar uma outra cópia de A no meu papel.
Então, eu volto no meu primeiro autômato e, onde isto era um estado final,
eu faço com que ele deixe de ser um estado final -- então eu mudo essa parte.
Então, eu vou adicionar uma trasição ε aqui, e vou apagar essa outra seta que indica que este é um estado inicial.
Agora eu tenho um novo autômato de estados finito, que aceita strings da seguinte forma:
deve haver uma parte -- x -- aqui, que seria aceita por A,
e depois outra parte, possivelmente diferente aqui -- y -- que seria também aceita por A.
Então, em geral, eu aceito x ε y -- ou xy.
De fato, eu sempre posso fazer isso.
Se você me dá qualquer autômato de estados finito A, eu sempre posso construir um autômato de estados finito duas vezes maior,
que aceita um string de A, seguido de outro string, independente, separado, também aceito por A.
Entretanto, este aqui é um pouco mais complicado.
Acontece que a resposta é: algumas vezes.
Deixe-me dar um exemplo de SIM e um exemplo de NÃO.
Digamos que o autômato de estados finito que você me dá como sendo B aceita apenas um string -- b.
Eu vou fazer o mesmo truque de antes. E agora eu tenho um novo autômato de estados finito, que aceita bb.
Como este é o único string da linguagem, eu agora o dupliquei. Isso funciona ok.
Eu posso fazer isso pelo menos em um caso. Mas agora vem a parte ruim.
Para este exemplo de B aqui em cima -- este em azui -- funcionou corretamente.
Mas agora eu vou dar um exemplo de B para o qual isso não funciona.
Aqui, B é a*x.
Este autômato de estados finito aceita a expressão regular a*x --
qualquer número de a's, possivelmente 0, seguido de um x.
Agora, note a diferença entre esta sentença e a anterior.
Isso requer exatamente o mesmo string duplicado.
Vamos imaginar que eu complete essa construção do autômato de estados finito --
o mesmo tipo de coisa que eu fiz antes.
Agora, eu vou escrever alguns strings que podem ser a*x duas vezes.
Bem, eu poderia não ter a's,-- então eu tenho nenhum a, seguido de um x.
Ou eu poderia ter um a -- isso parece ok, por enquanto --
Ou poderia ter dois a's, ou poderia ter três a's.
Esse padrão deveria parecer promissor.
Mas, em geral, se eu pudesse duplicar este autômato de modo que ele aceite o mesmo string nnas duas vezes,
ao invés de um novo string cada vez, eu poderia reconhecer (a^n)x(a^n)x.
Pela mesma razão que (a^n)(b^n) nãopode ser reconhecido -- não é regular -- também isso não pode.
Temos aqui um exemplo positivo e um exemplo negativo.
Portanto isso é verdade algumas vezes.
Isso foi um bem difícil. Não se sinta mal se você não viu isso de primeira.