Week 1 - Finite Automata

Question 1

What is a computational model?

Answer 1

An “idealised” computer that is used to set up a managable mathematical theory of computation.

Question 2

Give an example of a computational model.

Answer 2

The finite state machine (finite automaton).

Question 3

What is finite automata?

Answer 3

Models of computers with extremely limited memory.

Question 4

Define the components of a finite automaton in computational terms.

Answer 4

A finite automaton is a 5-tuple (Q, Σ, δ, q0, F), where
Q is a finite set of states.
Σ is a finite set called alphabet.
δ is a function (QxΣ -> Q), the transition function.
q0∈Q is the initial state of the machine.
F⊆Q is the set of final states of the machine.

Question 5

What is δ (transition function) in the finite automaton?

Answer 5

The function that decides what state the machine should go to next (Depending on the current state and the symbol it reads next).

Question 6

TRUE OR FALSE: There can only be one final state for the finite automaton.

Answer 6

FALSE, there can be any number of final states, even no final states.

Question 7

TRUE OR FALSE: There can only be one initial state for the finite automaton.

Answer 7

TRUE, there is only ever one initial starting state for the machine.

Question 8

TRUE OR FALSE: The initial state can be a final state.

Answer 8

TRUE.

Question 9

Describe the finite automaton in less computation mathematics terms.

Answer 9

It is a machine that starts in one state, and reads a certain input string. It reads the symbols one at a time, and with each symbol the machine may change state depending on the transition function. It ends once it has read the whole string.

Question 10

What is the purpose of a finite automaton?

Answer 10

It processes a given string and accepts or rejects it depending on whether or not the machine ended the process in a state that part of the set of final states.

Question 11

What is the F (Final states) for a finite automaton?

Answer 11

The set of states in the machine that if the process ended when in this state the machine could accept the input.
It is the set of final states.

Question 12

Define the language of a finite automaton machine.

Answer 12

The set of strings that that machine accepts.

Question 13

Why might a language be called regular?

Answer 13

A language is called regular if some finite automaton recognizes/accepts it.

Question 14

How do you define/write that a language is accept be a given machine?
Machine is M
Language is L

Answer 14

L = ℒ(M).