質問

I'm trying to solve this problem using Deterministic Finite Automata :

inputs:     {a,b}
conditions: 
a. must have exactly 2 a  
b. have more than 2 b

so a correct input should be like this abbba or bbbaa or babab

now my question is, "is there a pattern to solve this things?"

役に立ちましたか?

解決

Yes there is a pattern. You can take each statement and deduct pre-states from them. Then you take the cross-product of those pre-states, which will comprise the final states. In this example:

a. will yield states: 0a, 1a, 2a, 2+a (you've seen 0 a, 1 a, 2 as or more than 2 as) b. will yield states: 0b, 1b, 2b, 2+b (you've seen 0 b, 1 b, 2 bs or more than 2 bs)

The cross product of these states result in 4x4=16 states. You'll start from {0a,0b} states. The inputs can be 3 types: a, b or something else. From that you should be able to go. Do you need more help?

(Are we solving homework?)

他のヒント

Always draw such things first.

Feel free to give states any meanings. What you need here is states like: q2: (1 b, 2 a's). Draw states like this, until the accept state and connect them with lines. The accept state is qx: 2 a's 3 b's.

After reaching the accept state, if input is "b" that line goes to itself, the accept state. If the input is "a", draw a new state, that will get into an endless loop and goes into itself no matter what the input is.

(are we helping for an exam here?)

ライセンス: CC-BY-SA帰属
所属していません StackOverflow
scroll top