As always, I find the easiest way to answer such a question
is to draw the finite-state machine.
We come in in state 1, and on a we go to state 2.
And on b we go to state 3,
and then from state 2 on c
we go to 4, and state 3 on d we go to 5,
and 5 on e goes back to 2, and 5 on f
goes to state 6, and 5 on g
goes all the way back here to 1, and our only accepting state is 6.
Well, how can we get to state 6?
If we go up here to the right,
this is like the place of no return.
We go here, and then there's no way to ever get back down or get to 6,
so we don't want to go to 4.
We don't want to get to 2.
How about instead if we go 1, 3, 5, 6 or b, d, f?
But now I need to give another string
that's different but that's also accepted.
One way to do that would be to take this
go to start back loop here, pass go, start again.
1, 3, 5, 1, 3, 5, 6.
So b, d, g, b, d, f.
Those are 2 strings that are both accepted but that are different.
And if you are feeling exotic, you could actually have gone around these loops more times.
You can add b, d, g, b, d, g, b, d, g at the beginning as often as you'd like
and make longer and longer strings.
Come al solito, l'approccio più facile per questa domanda
è disegnare la macchina a stati finiti.
Siamo allo stato uno, con 'a' andiamo allo stato due.
Con 'b' allo stato tre,
e dallo stato due con 'c'
andiamo al quattro. Dallo stato tre con 'd' andiamo allo stato cinque.
E da cinque con 'e' torniamo allo stato due, e con 'f'
allo stato sei. Dal cinque con 'g'
torniamo tutto indietro ad uno; il nostro unico stato accettante è il sei.
Bhé, come raggiungeremo lo stato sei?
Se andiamo qui a destra,
siamo in un vicolo cieco.
Andiamo qui, e non c'è modo di tornare indietro al sei,
quindi non volgiamo finire nel quattro.
Non vogliamo andare al due.
E se invece andassimo uno, tre,cinque, sei; ovvero 'bdf' ?
Adesso devo trovare un'altra stringa
che sia diversa ma anch'essa accettata.
Una maniera per farlo sarebbe prendere
questa via che torna all'inizio, e cominciare di nuovo.
uno, tre, cinque, uno, tre, cinque, sei.
quindi 'bdgbdf' .
Queste sono due stringhe che sono entrambe accettate ma differenti tra loro.
E se ti senti eccentrico, avresti potuto andare in tondo per questo loop molte volte.
Puoi aggiungere 'bdgbdgbdg' all'inizio quante volte volessi,
costruendo stringhe più lunghe.
では有限状態機械を図式化して解説しましょう
これが一番分かりやすいのです
aかbでステート1からステート2へ遷移します
bを入れるとステート3へ移り
こちらはcを入力するとステート4へ移り
ステート3からはdでステート5へ遷移します
ステート5にe入れるとステート2に戻ります
ステート5にfを入れるとステート6に到達します
ステート5にgを入れるとステート1に戻りますが
受理ステートはステート6だけです
どうすればステート6まで遷移できるでしょうか?
もしステート1から右に進んでしまうと
戻る場所はなくなってしまいます
ステート4からはどうやってもステート6へ
遷移することはできません
ステート2からも遷移できないので
ステート1、3、5、6
b、d、fと遷移しましょう
文字列はもう1つ必要です
異なる文字列でステート6まで行くには
ループを使う方法があります
ステート5まで行って
また開始ステートに戻るのです
1、3、5、1、3、5、6
文字はb、d、g、b、d、fです
異なる内容ですが2つとも受理されます
もし変わった文字列を作るのであれば
何度もループを使うことができます
b、d、gを何度も繰り返して使うことで
長い文字列を作ることができます
Como sempre, acho que o modo mais fácil de obter a resposta desta questão
é desenhar o FSM.
Começamos no estado 1 e, com `a', vamos para o estado 2.
E com`b', vamos para o estado 3,
e então, do estado 2, com `c',
vamos para o estado 4; do estado 3, com `d', vamos para o estado 5;
de 5, com `e', voltamos para 2; de 5, com `f',
vamos para o estado 6 e de 5, com `g',
voltamos para o estado 1. O estado de aceitação é 6.
Bem, o que podemos obter no estado 6?
Se vamos aqui para a direita,
este estado não tem saída.
Se chegamos aqui, não há como ir até o estado 6.
Então não queremos ir para o 4.
E também não queremos ir para o 2.
E se formos para 1, 3, 5, 6, ou seja, `b', `d', `f' ?
Mas agora temos que dar outro string,
diferente, e que também seja aceito.
Uma maneira de fazer isso seria tomar
este caminho, para vaoltar aqui, e então começar de novo.
1, 3, 5, 1, 3, 5, 6.
Ou seja, `b', `d', `g', `b', `d', `f'.
Esses são 2 strings que são aceitos e são distintos.
E se você for mais exótico, pode voltar neste loop mais vezes.
Voc6e poderia adicionar `b', `d', `g', `b', `d', `g' no iício, quantas vezes quiser,
e formar strings mais e mais longos.
通常,我觉得回答这样一个问题最容易的方法是
画出这个有限状态机
我们从状态1开始,对于输入a,移到状态2
对于输入b,移到状态3
对于输入c,从状态2移到
状态4,对于输入c,从状态3输入到状态5
对于输入e,从状态5回到状态2,对于输入f,
从状态5移到状态6,对于输入g,从状态5
一直返回到状态1,而我们唯一的接收状态是6
好的,我们如何能得到状态6呢?
如果我们从这往右边走,
这看起来是不会返回的
我们来到这,是没有方法返回到状态6的
所以我们不想移到状态4
我们不想移到状态2
如果我们是沿着1,3,5,6或者b,d,f来走呢?
但现在我需要给出另一个不同的字符串
而它又是能被接受的
一种方法是从这里开始
再循环到这里,然后再来一遍
1,3,5,1,3,5,6
就是b,d,g,b,d,f
这两个字符串都能被接受,而又不相同
如果你感到奇怪,实际上你可以沿着这个循环几次
你可以多次添加b,d,g,b,d,g,b,d,g
使得字符串越来越长