Finite State Machine Homework For Kids

Presentation on theme: "Finite State Machines Concepts DFA NFA."— Presentation transcript:

1 Finite State MachinesConceptsDFANFA

2 Graphs and MoreFinites state machines are directed graphs.

3 Nodes-states, Edges-input
Each city represents a state you can be in.Take and edge on some desire(input)Imagine you are doing a food tour of the country, starting in AtlantaYou want to eat…Perogies, Philly Cheese Steak, Cuban

4 Edges as input What kind of questions can we answer!
The food transitions are along the pathway.Certain food tours are allowed, others just don’t work out!Valid: Perogies, Philly Cheese Steak, Miami CubanInvalid: Perogies, Jambalaya, CubanSame food can be found in several places, and assume there is a finite set of foods – the alphabetThere are also a finite set of cities that you can be in, or go to – the statesAdd restriction that for health reasons, the last food you eat has to be Cuban! ( ACCEPTING vs REJECT states)What kind of questions can we answer!

5 Finite State Machines (FSMs)
What are the problems we are trying to solve?Acceptor – takes an input and tells you whether the input matches some specifications. (Are you in or are you out)Transducers – working thru input data to modify the behavior of some process.Key limitation - memory size is fixedIndependent of input size.Input StringFSM{Yes, No}

6 The FSM model Inputs: Machine: A directed graph Special states 1 2 FSM
Strings built from a fixed alphabetMachine: A directed graphNodes: states of the machineEdges: transitions from one state to anotherSpecial statesStartFinal or accepting12aba,bInput StringFSM{Yes, No}

7 FSM Decider Example Which strings of as and bs are accepted? 2 1
Input alphabet {a, b}States {q0, q1, q2}Start state q0Final states {q2}aa21bba,b

8 The soda machine – concretely

9 The soda machine – abstractly
Input alphabet$0.25Return-coinStatesReady-for-coins2550Empty…

10 Making the DFA model precise
 Input alphabetS State setq0  S Initial stateF  S Final states:S    S Transition functionM = (, S, q0, F, )

11 Building FSMs An FSM is a directed graph How to minimize space?
How large is the input alphabet?How many states?How fast must it run?How to minimize space?RepresentationsMatrixArray of listsHashtableOverlapping hashtableSwitch statementab1234

12 Representing the machine
Matrix representationWhy?Running Time?ab12

13 Process machines Coke machine
Speech recognition – add probability to the transitionsTCP protocolParsers (HTML)

14 TCP Protocol ( don’t worry …)

15 Deciders“Are you IN or are you OUT”- Jerry Maguire

16 Simple DFA example HTML Parser – Is it valid HTML?
Accepts strings that end in 1 , å= {0,1}Create a machine that accepts string which contain the sub-string “001”0010, 1001 are in.11, 0000 are outWorking it out… Skip all 1’s, perk up when you see a 0. ( you may have just come upon the substring ). Skip back if you see a 1 too early.1. Seen no symbols of the pattern2. Just seen a 03. Just seen a 004. Just seen the entire pattern 001

17 Regular Expressions Regular expression.
Way to describe sets of stringsExamples –(“|” – OR)(“*” – 0 or more, “+” – one or more)(01)*(a|b)*abthis | that | theother00*11*22* =

18 Languages and FSMsA language that can be DECIDED by an FSM is called regular.Examples(accepts only these and no other)a(a|b)*bEasiest way to test whether a language is regular is to see if you can create a machine!L = {a(a|b)*b}

19 Problems types What about… a(a|b)*b What does this mean? | - OR
* - 0 or more

20 Problems types Ends with… (a+b)*ab Begins with… ab(a+b)*
Contains substring ‘w1’ (a+b)*w1(a+b)*Even / odd numbers of some character or both!Leverage the power of the guess

21 Enhancing the model - NFA
Non-determinismAllow the machine to be in more than one state at onceOn a given input, you could follow multiple pathsIf there EXISTS a pathway to an ACCEPT state to deal with the given input, ACCEPTExamples:001 sub-stringa(a|b)*b

22 The Idea of Non-determinism
An NFA can be in more than one state at a time3 ways of looking at itCoins/fingers on every state you can be at.A tree of outcomes, put a lemming on each path, if any of them end on a final state, we ACCEPTOracle approach. Someone is telling you the right way to go

23 I like lemmings…Lemming approachDeterministicNon-deterministic…

24 More examples “[.?!][]\"')]*\\($\\|\t\\| \\)[ \t\n]*”
[.?!][]\"')]*($|<tab>|)[<tab><C-j>]*Emacs regexp:Any of . ? ! followed byZero or more of ] “ ‘ ) followed byAny of end-of-line, tab, two spaces followed byZero or more of space, tab, newline

25 Big QuestionAre there languages L that can be accepted by NFAs but not DFAs?Are they more “powerful”?

26 Big QuestionAre there languages L that can be accepted by NFAs but not DFAs?No!

27 What have we gained? Can we solve harder problems?
We have assumed we can solve problems by only parsing the data once…What about the ability to back-track? Turing Machines… ( If I only had a memory…)

28 What can’t you do Counting (on an unbounded set) L = {0n1n | n>0}
It needs to remember the number of 0’s it has seen. Since the number of 0’s is not limited we would have to track an infinite set of states.Violates our memory condition…We can do L = {0515}

29 What can’t you do Counting (on an unbounded set) L = {0n1n | n>0}
It needs to remember the number of 0’s it has seen. Since the number of 0’s is not limited we would have to track an infinite set of states.Violates our memory condition…We can do L = {0515}NEED MORE POWER

30 End

Unformatted text preview: CDA 3201 Computer Logic Design Fall 2016 Solutions to Homework 5 Points: 100 Questions 1 to 5: 17 points each. Q6: 15 points 1. A Mealy Finite State Machine (FSM) has two binary inputs X1 and X2 and one output. The machine outputs a 0 and resets to 00 state whenever it receives two consecutive input strings that are identical (for example 01 followed by 01). In all other cases it outputs a 1. Use the following convention to label each state: Label the state as PQ if it is reached after receiving two input strings X1X2=P and X1X2=Q where P and Q are the decimal values of X1X2. Note that P and Q range from 0 to 3; for example, if the previous two inputs to a state are 01 and 11 it is labeled as 13. For states which are children of 00 (reset) use P=0 irrespective of how the 00 state is reached. Draw the FSM clearly labeling all inputs, outputs and state names but to decrease clutter DO NOT draw any outgoing transitions from states 20,21,23,30,31,32. Hint: the FSM has more than 10 states but its structure is simple and repetitive. 2. A sequential machine operates with an overlapping sliding window and has 1 input (X) and two outputs (Z1 and Z2) which have a default value of 1. An output Z1=0 occurs every time the input sequence 100 is completed provided that the sequence 011 has never occurred. An output Z2 = 0 occurs every time the input 011 has occurred. But once the sequence 011 has occurred, Z1 is permanently reset to 1 and will not change even if a sequence of 100 occurs. Draw the Mealy state graph with no more than 8 states and the corresponding state table. Example input: 100110011. Corresponding Z1 output: 110111111; Z2 output: 111101110. 11 11 11 01 11 11 11 11 11 11 11 10 11 11 10 11 State S0 S1 S2 S3 S4 S5 S6 S7 When this point is reached in the graph, 011 has been received and we are only looking for 011 to occur again. Meaning Reset Prev input was 0/011 has not occurred Prev input was 01/011 has not occurred No sequence / 011 has occurred Prev input was 0/011 has occurred Prev input was 01/011 has occurred Prev input was 1/011 has not occurred Prev input was 10/011 has not occurred Next State X=0 X=1 S1 S6 S1 S2 S7 S3 S4 S3 S4 S5 S4 S3 S7 S6 S1 S2 X=0 11 11 11 11 11 11 11 01 Z1Z2 X=1 11 11 10 11 11 10 11 11 3. A Moore machine has an input (X) and outputs (Y and Z). YZ represents a 2 bit binary number equal to the number of 1's that have been received as inputs. The circuit resets when the total number of 1's received is 3 or when the total number of 0's received is 3. Draw the state graph and state transition table for the machine. ** Horizontally: Number of 1’s modulo 3. ** Vertically: Number of 0’s modulo 3. State S0 S1 S2 S3 S4 S5 S6 S7 S8 Next State X=0 S3 S4 S5 S6 S7 S8 S0 S0 S0 YZ X=1 S1 S2 S0 S4 S5 S0 S7 S8 S0 00 01 10 00 01 10 00 01 10 4. A FSM receives one bit of data at each clock cycle and outputs a 1 when the sequence 11 or 1001 is received. It resets to start state after detecting either one of these two sequences. i) Draw the Mealy state diagram ii) Implement the FSM using D flip flops by deriving the minimized next state and output logic functions. Present State/D1D0 A/00 B /01 C/11 D/10 Next State/Output X=0 X=1 A/0 B/0 C/0 A/1 D/0 B/0 A/0 A/1 D1+D0+ X=0 X=1 00 01 11 00 10 01 00 00 From the State Transition Table above, we can determine the logic functions for Next State, D1+ and D0+ shown below: D1+ = D0 X' D0+ = D1' D0' X + D1' D0 X' + D1 D0 X Z = D1' D0 X + D1 D0' X 5. The decimal digits 0 through 9 are encoded as 4-bit binary numbers. They are transmitted in disjoint windows of length 4 with the least significant bit first and are input to a Mealy circuit. The circuit generates an output of 1 (0) when the fourth bit is received if the 4 bits have been even (odd) parity; the circuit output is a Don't-Care for the first 3 bits. Construct an incompletely specified table for the circuit. A simpler implementation shown below requires branching to two separate states after each bit is received except for the last bit (MSB). This requires 15 states. However a more compact representation is possible by observing that we only need to keep track of the parity (except we must not include paths for bit strings which do not occur in a BCD string) as shown below. 0/- 6. Design the state diagram for the control unit of a coin-operated Coke machine. Coke costs 125 cents and the machine accepts quarters and dollars. Change should be returned if more than 125 cents is deposited. Assume that the machine dispenses the product and change, if any, and resets once at least 125 cents are deposited. ‡–ƒ†”‡’”‡•‡–‹•‡”–‹‘‘ˆ—ƒ”–‡”ƒ†‘ŽŽƒ””‡•’‡…–‹˜‡Ž›Ǥ‡–—•ƒ••—‡ –Šƒ–‘Ž›‘‡…‘‹…ƒ„‡‹•‡”–‡†ƒ–ƒ–‹‡Ǥ‘–Š‡–Š”‡‡’‘••‹„Ž‡–”ƒ•‹–‹‘•ˆ‘”–Š‡ ƒ”‡̵̵ȋ™ƒ‹–‹‰ˆ‘”…‘‹Ȍǡ̵ǡƒ†̵Ǥ‘••‹„Ž‡•‡“—‡…‡‘ˆ…‘‹‹•‡”–‹‘–‘ ‰‡–ƒ‘‡™‹–Š‘—–ƒ›…Šƒ‰‡”‡–—”‡†ƒ”‡ǡǡƒ†Ǥ‡“—‡…‡•–Šƒ– ”‡–—”…Šƒ‰‡ƒ††‹•’‡•‡‘‡ƒ”‡ǡǡǡƒ†ǤŠ‡—–’—–•ƒ”‡ ƒ†”‡’”‡•‡–‹‰”‡Ž‡ƒ•‡‘ˆ‡˜‡”ƒ‰‡ƒ†Šƒ‰‡”‡•’‡…–‹˜‡Ž›ǤŠ‡•–ƒ–‡ †‹ƒ‰”ƒ‹••Š‘™„‡Ž‘™ȋ–”ƒ•‹–‹‘•̵ƒ†̵ƒ”‡†‡‘–‡†ƒ••‹’Ž›ƒ†ȌǤ ...
View Full Document

0 Replies to “Finite State Machine Homework For Kids”

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *