FSM, Regular expressions, BNF

Question 1

What is a moore machine?

Answer 1

Outputs at each state (including when it starts)

Question 2

what is a mealy machine?

Answer 2

The outputs are from the transitions

Question 3

Why are FSM’s useful?

Answer 3

model many kinds of task eg a language, controller, protocols, spellcheck.

Question 4

Define FSM?

Answer 4

Consiits of a set of inputs symbolsa, and produces a set of output symbols.

Finite number of stats with tranition rules

can have an output or not.

Question 5

What is a halting state in a fsm

Answer 5

A state that has no outgoing transiitons

Question 6

What is a non-deterministic FSM?

Answer 6

An fsm that may have several possible next states for each pair of state and input symbol.

(eg an input of 1 has 2 transitions, and which it does is decided by weather the fsm can get to the acceptor)

Question 7

Deterministic FSM

Answer 7

has one next state for each input

Question 8

What is a FSA?

Answer 8

Finite state automaton

an fsm which has no output until the end where it outputs yes or no.

(yes producing states are the accepting states)

Question 9

What is a regular expression?

Answer 9

a notation for defining all the valid strings of a formal language or for defining a search pattern

Question 10

What does | mean in regular equarssions?

Answer 10

or (has the lowest priority)

Question 11

What does * mean in regular equarssions?

Answer 11

0 or more

Question 12

What does ? mean in regular equarssions?

Answer 12

0 or 1

Question 13

What does + mean in regular equarssions?

Answer 13

1 or more

Question 14

What does ( ) mean in regular equarssions?

Answer 14

grouping

Question 15

what does [] mean in regular expressions?

Answer 15

Whats inside the brackets is the class, and shows all allowable characters eg [ae] is a or e.

[a-z]-lowercase

[a-zA-Z]any letter

Question 16

what does [^] mean in regular expressions?

Answer 16

anything but eg [^t] is anything but t

Question 17

what does \d mean in regular expressions?

Answer 17

any numeric character

Question 18

what does \w mean in regular expressions?

Answer 18

any alpha numeric character

Question 19

what does \s mean in regular expressions?

Answer 19

space

Question 20

what does \W (captital) mean in regular expressions?

Answer 20

its not \w or [^\w]

Question 21

what does . mean in regular expressions?

Answer 21

it matches any character

Question 22

applications of regular expressions

Answer 22

• searcing for files
• searching for words in a block of text
• searching for virus signatures
• filtering text

Question 23

What is a turning machine?

Answer 23

An FSM that controls one + tapes that are infinite and can move in both directions. Can execute any algothrithm

Question 24

What does a TM do at each step?

Answer 24

• Changes state
• Changes symbol on tape
• Moves the tape 1 step (or doesnt move)

Question 25

What problems cana TM solve?

Answer 25

any computable problem will have a Tm that will halt with the correct output for all inputs

Question 26

Transition lables for a TM

Answer 26

input,Input | Outputs Direction eg 1,0 | # \<--

Question 27

Whats a halting state in a Tm?

Answer 27

Double circle. It stops the machine

Question 28

Transition rule format for TM

Answer 28

𝛿( CurrentState, On Tape ) = (NextState,output,movetape) eg 𝛿(S0,{0,1})=(S1, ,-\>)

Question 29

What is a transition table

Answer 29

A table that shows each state, and where each input will take the machine and what output it gives

Question 30

what is a universal Turing machine?

Answer 30

A turing machine that can execute other turning machines, by first inputting the transition rules then the data. (Interpriter reads rules of the TM its simulating) (program is fed into it like data)

Question 31

What is BNF?

Answer 31

backus-Naur form a notation for expressing the rules for constructing valid stings in a regular langeage (defines the syntax)

Question 32

BNF format

Answer 32

: : = Definition

Question 33

How would recursion work in BNF? | (1 or more of somehting happeneing)

Answer 33

::= |

Question 34

What is a parse tree?

Answer 34

A pictorial representation showing how a valid thing conforms to the rules. (a break down of the input and what groups each section will belone to, with the smallest group being at the bottom of the tree, and then the input is there.

Question 35

What is a Syntax diagram

Answer 35

ALternative way to define syntax (visual BNF)

Question 36

Syntax diagram and its symbols

Answer 36

In circle is the words that are needed In rectangles are the other defined things.