Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A finite state machine.

  1. Apr 23, 2006 #1
    Why is it not possible to construct a finite state machine that recognizes precisely those sequences in the language
    A = {0^i 1^j |i,j Element Z^+, i>j} where the alphabet for A is {0,1}..

    I just don't get it why this is not possible.. :grumpy:

    Is it because 0 can be infinite.. ?
     
  2. jcsd
  3. Apr 23, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    0 is 0, 0 is not 'infinite'.
     
  4. Apr 23, 2006 #3
    yeah i know that, but in a finite state machine... According to the sequence in the language there must be more 0 than 1... (the way I understand it..)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook