Join TSR now and get all your revision questions answeredSign up now
    • Thread Starter
    Offline

    1
    ReputationRep:
    Hi,

    I'm stuck on two questions and I really can't seem to get my head round them.
    1. Figure 1.3.6 shows an FSM and the state transition diagram with which it is programmed. The machine accepts input sequences consisting of the letters a and b, e.g. aabbbabaab. The machine has a lamp labelled ACCEPT. The machine starts out in state 1 and the accepting state is also state 1. When the machine is in state 1 after the machine has exhausted the input, the lamp lights. What does this machine detect and indicate with the lamp?
    Name:  fsm.png
Views: 628
Size:  37.5 KB

    2. Draw state transition diagram with output for an FSM that gives an output of 1 if and only if the input string read so far ends with 111 otherwise it gives an output of 0.

    Thank you very much for any help that you can give!
    • Study Helper
    Offline

    21
    ReputationRep:
    (Original post by m00c0w)
    Hi,

    I'm stuck on two questions and I really can't seem to get my head round them.
    1. Figure 1.3.6 shows an FSM and the state transition diagram with which it is programmed. The machine accepts input sequences consisting of the letters a and b, e.g. aabbbabaab. The machine has a lamp labelled ACCEPT. The machine starts out in state 1 and the accepting state is also state 1. When the machine is in state 1 after the machine has exhausted the input, the lamp lights. What does this machine detect and indicate with the lamp?
    Name:  fsm.png
Views: 628
Size:  37.5 KB

    2. Draw state transition diagram with output for an FSM that gives an output of 1 if and only if the input string read so far ends with 111 otherwise it gives an output of 0.

    Thank you very much for any help that you can give!
    Looks like its an even parity check for 'a' within a string by toggling on an input of 'a'.

    Follow the sequence through:


    Machine starts out and stays in state 1 until 'a' (odd number of a) appears at the input.......

    At which point it jumps to state 2, but stays in this state until another 'a' appears (even number of a) at which point it jumps back to 1 and stays in this state until until another 'a' (odd number) is input. It does this flipping until the input character string is exhausted.

    The machine accepts the string only if there was an even number of 'a' characters in the string.

    Does that make sense?


    Therefore the machine detects an even parity of 'a' in an indefinite string of characters.

    Q2. Use the above to work out the transition diagram to look for a string of 111. Hint, how many decision bubbles will be needed? Where will the closed loops to remain in the same state be?
 
 
 
Poll
If you won £30,000, which of these would you spend it on?

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.