ICSI 409 - Formal methods Midterm

Terms and definitions

FA is a 5-Tuple

Q, Σ, δ, q₀, F

Q

A finite set of states

Σ

A finite alphabet

δ

A state transition function

q0

The initial state

F

The set of accepting states

What is a regular language?

1. it can be read/recognized by a finite automata machine

2. It can be described by a regular expression

Finite automaton

A mathematical model that consists of a finite
set of states, a set of input symbols (also called an alphabet), and a
set of transitions between states that are triggered by the input
symbols.

When are regular languages used?

When a problem can be solved with finite memory

Two types of FA

DFA - Deterministic Finite Automata

NFA - Non-Deterministic Finite Automata

4 rules for building a DFA

1. The automaton must have a finite number of states, represented as circles on a diagram

2. The automaton must have a set of input symbols, which can be represented arrows between states. The input symbols are the alphabet of the automaton.

3. There must be a start state, which is the initial state of the automaton. This state represented by an arrow pointing to it.

4. There must be one or more accepting states, which are the final states of the automaton. These states are represented by a double circle

5. The transition between states must be defined by a transition function, which maps each state and input symbol to a new state.

6. The transition between states must be deterministic,

7. The automaton must be minimal.