FIT2014 Lecture Notes - Lecture 6: Deterministic Finite Automaton, Regular Expression
28 Jun 2018
School
Department
Course
Professor
Lecture 6: Finite Automata
Finite Automaton
- FA is also as know as Deterministic Finite Automaton
- Used to determining whether a word does or does not belong to a Regular Langing
- Used to defining Regular Language
- Used in Lexical Analysers
Definition:
- A finite set of states
o One called the Start state
o Some (maybe none) called Final States
- An Alphabet of possible input letters
- A finite set of transitions
o That tell, for each state and each letter in the alphabet
which state to go next
o There is a unique transition from any state for each letter in
the alphabet
Every string traces a unique path in the automaton, starting from the Start State and following the transitions,
letter by letter.
1. A string is accepted by a FA if its path ends on a Final State. Otherwise the string is rejected.
2. The language recognised by a FA is the set of all strings it accepts. We say the FA recognises the
language, or accepts the language.
Special Cases:
- All words accepted.
- Only the empty word accepted.
- A single word accepted.
Complement Finite Automaton (FA)
- Suppose some FA accepts the language L
- Change all the final states in this FA to non-final states, and all the non-final states to final states.
- This new FA now accepts all the strings not accepted by the original FA (ie. all the words in ¬𝐿 ),
and rejects all the words that the original accepted (i.e., the words in L).
- So the new FA accepts . ¬𝐿
With Regular Expression :
- It is easier to write down a regular expression that define a language than to design a FA to
accept this language
Document Summary
Fa is also as know as deterministic finite automaton. Used to determining whether a word does or does not belong to a regular langing. A finite set of states: one called the start state. A finite set of transitions: that tell, for each state and each letter in the alphabet which state to go next, there is a unique transition from any state for each letter in the alphabet. Every string traces a unique path in the automaton, starting from the start state and following the transitions, letter by letter: a string is accepted by a fa if its path ends on a final state. Otherwise the string is rejected: the language recognised by a fa is the set of all strings it accepts. We say the fa recognises the language, or accepts the language. Change all the final states in this fa to non-final states, and all the non-final states to final states.
