CS 390 Midterm Review

Module 2

Finite Automata

a mathematical model of computation based on the ideas of a system changing state due to inputs supplied to it. Some of these states are acceptor or final states

Finite Automation

a collection of states in which we make transitions based upon input symbols. Defined as a 5-tuple (Q,Σ,q0,A,δ) 

Q

finite set of states

Σ

finite input alphabet

q0∈Q

the initial state

A⊆Q 

the set of accepting states

δ:Q×Σ→Q 

the transition function

Regular language

a language is regular if there’s a DFA that accepts it. It can be described by a regular expression. Example: Strings ending in “01,” even number of 0s, and strings with “001” substring

death state

a non-accepting state that absorbs all invalid inputs

DFA characterisitcs

• Deterministic: single transition per state/symbol

• Fast: O(n) time complexity for scanning

• Memory: O(m) for pattern length m

NFA characteristics

• Non-deterministic: multiple possible transitions

• Flexible: can handle complex patterns

• Backtracking: may need to explore multiple paths

NFA

non-deterministic finite automation.

• multiple transitions: from a state, can go to multiple states on same input

• e-transitions: can move to another state without consuming input

• non-deterministic: multiple possible paths for same input