FIT2014 Lecture Notes - Lecture 7: Regular Expression
28 Jun 2018
School
Department
Course
Professor
Lecture 7 Kleene’s Theorem
Any language can be defined by
- Regular Expression
- Finite Automata
- NFA
- GNFA
Can be defined by any of the other methods.
Converting a Regular Expression to NFA
Converting NFA to FA
In FA :
- Any string w traces a unique path, starting from SS and ending at some unique path. Which we
will call endState(w)
- The string w is accepted If endState(w) is a final state, otherwise is rejected
In NFA :
- Any string w traces a set of paths, starting from the SS and send at some set of states which will
call endState(w)
- The string w is accepted endStates(w) contains a final States, otherwise is rejected.
Generalisaed Nondeterminstics Finite Automaton
Definition A Generalised Nondeterministic Finite Automaton (GNFA) is a NFA in which:
- transitions are labelled by regular expressions, not just by single letters;
- there is just one Final State, and it is not the Start State;
- there are transitions from every state to every other state (including itself), except that the Start
State has no incoming transitions and the Final State has no outgoing transitions. (Note: you can
just label a transition by Ø if you don’t want to use it.)
Definition
A string w is accepted by a given GNFA if it can be divided into substrings, w = w1…wk, such that there is some
sequence of transitions, starting at the Start State, finishing at the Final State, and labelled by regular
expressions R1, …, Rk, such that, for all i, wi matches Ri . If a string w is not accepted by the GNFA, then it is
rejected.
Document Summary
Can be defined by any of the other methods. Any string w traces a unique path, starting from ss and ending at some unique path. The string w is accepted if endstate(w) is a final state, otherwise is rejected. Any string w traces a set of paths, starting from the ss and send at some set of states which will call endstate(w) The string w is accepted endstates(w) contains a final states, otherwise is rejected. State has no incoming transitions and the final state has no outgoing transitions. (note: you can just label a transition (cid:271)(cid:455) if (cid:455)ou do(cid:374)"t (cid:449)a(cid:374)t to use it. ) If a stri(cid:374)g (cid:449) is (cid:374)ot a(cid:272)(cid:272)epted (cid:271)(cid:455) the gnfa, the(cid:374) it is rejected. Given a fa: add a (cid:374)e(cid:449) fi(cid:374)al tate, add (cid:374)e(cid:449) tra(cid:374)sitio(cid:374)s la(cid:271)elled fro(cid:373) the pre(cid:448)ious fi(cid:374)al tates to this new one, and make those states no longer final. So now there is just one final state: add (cid:374)e(cid:449) ar(cid:272)s (cid:862)e(cid:448)er(cid:455)(cid:449)here(cid:863), la(cid:271)elled .
