L6 - Finite State Automata

Question 1

How do you show an accept state on a state diagram?

Answer 1

A double circle

Question 2

How do you show a start state on a state diagram?

Answer 2

Arrow pointing to the start state

Question 3

How do you show a transition and transition condition on a state diagram?

Answer 3

A curved arrow between states; put the condition on the curved arrow

Question 4

Is is required to have a start state or accept state?

Answer 4

No. Can have none.

Question 5

What is the maximum number of

a) Start States
b) Accept states

Answer 5

a) One.
b) Unlimited.

Question 6

State machines are what type of Automata?

Answer 6

Finite

Question 7

What are the five elements of a finite automaton?

Answer 7

Q - a finite set of states

Σ - finite set called the alphabet, the elements of which are called symbols

δ - a function called the transition function

q - an element of Q called the start state

F - a subset of Q called the accept states

Question 8

Why do we not hear about infinite automata?

Answer 8

‘uncountable’ states and transitions - impractical to consider

Question 9

What makes a finite automata a non-deterministic finite automata (DFA)?

Answer 9

• one input can lead from a given state to more than one states
• a transition may occur without an input
• input may be empty

Question 10

What makes a finite automata a deterministic finite automata (DFA)?

Answer 10

• one input will lead to one transition at most for any given state (one input cannot lead to two states)
• transitions only occur with input
• input may not be empty

Question 11

What is a language, in terms of finite automata?

Answer 11

A set of input strings.

Question 12

What makes a language a regular language?

Answer 12

If there exists a finite automaton that accepts the strings in the language, the language is regular.