1

I need help with this solution cause I've just begun studying the finite state automation and couldn't help myself with this problem.

does the question mean that I've to give input 1101 1101 & if so how to show the other state to go to if the bit string is not starting with two D's

Shashank Jha
  • 83
  • 1
  • 10

1 Answers1

0

Assuming D means the hexadecimal representation of the decimal number 13, then yes, the binary representation of the same number is 1101 and the set of strings beginning with two Ds (meaning, the hexadecimal representation of the binary string begins with two Ds) would be the set of strings beginning 11011101. To accept such strings with a DFA you need ten states:

  • an initial state
  • one state for each symbol in your string
  • a dead state

The transitions will go from the initial state to each state corresponding to symbols of your string, in order, on the symbols at those positions. Any input that's out of place will lead to the last, dead, state, which loops to itself. The only accepting state is the one corresponding to the last symbol of your string, and it loops to itself as well (since any string formed by appending to this base is also a string in your language)

Patrick87
  • 27,682
  • 3
  • 38
  • 73