x Turn on thread page Beta
 You are Here: Home

# AQA Computing Finite State Machines help watch

Announcements
1. 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?

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!
2. (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?

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?

Turn on thread page Beta
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: March 15, 2013
Today on TSR

### Are these types of degrees the future?

What are your thoughts?

Poll
Useful resources

## Make your revision easier

Can you help? Study Help unanswered threadsStudy Help rules and posting guidelines

## Groups associated with this forum:

View associated groups

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