If I have to draw a deterministic finite automata using a state diagram so that accepts a language, for example {λ ε {a,b}*: the word λ contains an even number of a and an odd number of b}, how do I know how many states I have?
質問する
412 次
1 に答える
1
4州で十分です。同時に満たす必要がある 2 つの条件があります。偶数の a と奇数の b です。互いに関係なく、各条件は true または false のいずれかになります。
trueを 1、falseを 0 で表すと、4つの異なる可能性が得られます。両方が false、どちらか一方が true、または両方が true です。したがって、真理値表が得られます。
even a | odd b
---------------
0 0
0 1
1 0
1 1
q[0, 0]最初の行を、2 番目などで表しq[0, 1]ます。次に、各状態の遷移を指定し、初期状態を特定する必要があります。
現在の状態に関係なく、可能な入力はaまたはbの 2 つです。したがって、状態ごとに 2 つの遷移を指定する必要があります。
ここで、初期状態は、入力を消費する前の状態です。0 は偶数なので、初期状態はq[1, 0]です。私たちの受け入れ状態は、両方の条件が満たされたときq[1, 1]です。
最後に、状態遷移があります。
q[0, 1]私たちの初期状態です
q[1, 0] reads b -> q[1, 1]
q[1, 0] reads a -> q[0, 0]
q[1, 1]私たちの受け入れ状態です
q[1, 1] reads b -> q[1, 0]
q[1, 1] reads a -> q[0, 1]
q[0, 1]この状態は、少なくとも1 つの aを読み取った場合にのみ到達します。
q[0, 1] reads b -> q[0, 0]
q[0, 1] reads a -> q[1, 1]
q[0, 0]この状態は、少なくとも1 つの aを読み取った場合にのみ到達します。
q[0, 0] reads b -> q[0, 1]
q[0, 0] reads a -> q[1, 0]
于 2016-07-16T16:10:39.777 に答える