Regular Languages and Finite State MachinesPlan for the Day:• More on Mealy Machines• An introduction to nondeterministic FAs• Regular Expressions• Properties of Regular Expressions• Applications”The first 90% of the code accounts for the first 90 % of the development time. The rema i ning10% of the code accounts for the o ther 90% of the development time.”- Tom Car gill1Finite St ate TransducersA Mealy machine outputs a finite sequence of symbols fro m its output al phabet as it m akeseach transition.A Mealy machine M computes a function f if, as it reads an input string w, its outputstring is f(w).Example: Generate parity bit sDefine a Mealy machine that adds an odd pari ty bit to every 4 bit block it reads. (That is, theparity o f the res ulti ng 5 bit block is odd).2Nondeterministic FAs, or NFAsTo get an NFA, we modify our DFA model to allow:• 0, 1 or multiple transitions from a state, gi ven an i nput symbol• Jumps from one state to another without processing any input symbol (ǫ-transitions)• This means that the transit ion function δ for an NFA is δ : Q × Σ → 2Q, where 2Qdenotesthe power s et of Q• For a st a te q and input symbol a, δ( q, a) is a set: δ(q, a) ⊆ QAn NFA accepts an input string if some choice of transitions corresponding to the string leadsfrom the start state to a final state.3NFA ExampleExample: State diagram for NFA N0 1 23a, ba aa, bbbFigure 1: NFA N - note that δ(0, a) = {0, 1}, δ(1, b) = ∅Question: What is L(N)?4ǫ-Jumps in NFAsAn NFA can have tra ns itions labeled ǫ. If there is an ǫ-transit ion fro m state q to state s, thenthe machine can move from q to s without processing any input.01q spεεFigure 2: NFA N2Question: What is δ(q, a)? What is δ(q, ǫ)?Exercise: What is L (N2)?Exercise: How can N2process input str i ng bb?5NFAsDefinitio n: A non-determinist i c finite automaton or NFA i s a 5-tuple (Q, Σ, δ, q0, F )where1. Q is a finite set of sta tes2. Σ is a finite alphabet3. δ : Q × (Σ ∪ {ǫ}) → 2Qis the transition function4. q0∈ Q is the sta r t stat e5. F ⊆ Q is the set of final stat es6NFA ExampleExample: NFA N0 1 23a, ba aa, bbbFormal definition o f N:N = ({0, 1, 2, 3}, {a, b}, δ, 0, {2, 3}) where δ is defined bya b ǫ0 {0, 1} {0, 3 } ∅1{2} ∅ ∅2{2} {2} ∅3∅ {3} ∅7Equivalenc e of NFAs and DFAs: Proof SketchFor any NFA N = (Q, Σ, δ, q0, F ), we will describe how to construct an equivalent DFA, i.e.,a DFA that has the same language as t he NFA.Note: Since an NFA can move to any state in a set of states on a transiti on, the states in ourconstructed DFA correspond to sets of states in the NFA.Part of an NFA NεaaaqrvtLet δ′be the tr a ns ition function for N’s equivalent DFA D. Pictured above is part of N’sdiagram - it includes all transitions l abeled a from state q, and all states reachable from q byfollowing an a transiti on and then ǫ jumps. So δ′({q}, a) = {q, r, t, v}.8Equivalenc e of NFAs and DFAsIn the constructed DFA, with transiti o n function δ′:1. The sta r t state is the set contai ning t he NFA’s star t state q0, and all states reachable f r omq0via ǫ-jumps.2. A state in the DFA is final if it contains one or more of the NFA’s final states.3. δ′(S, a) is the set containing all elements of Q that are reachable from a state in S byfollowing an a-arrow and then zero or more ǫ arrows.At every step of computation, D enters a state that corresponds to the set of st a tes N couldbe in at that point in the processing of the input string.9Construction ExampleExample: Given the NFA N below, we will construct an equivalent DFA, i.e., one that a c-cepts exactly the same strings as the NFA.123a, bb, cεε10Regular Expres sionsRegular expressions are expressions that describe languages.Definitio n: R is a regular expressio n over alphabet Σ if R is1. a for some a ∈ Σ2. ǫ3. ∅4. R1∪ R2(also denoted R1|R2), where R1, R2are regular expressions (R1∪ R2describesthe union of the languages represented by R1and R2)5. R1R2, where R1, R2are regular expressions (R1R2represents the concatenation of R1’slanguage with R2’s language)6. R∗1, where where R1are regular expressionsNote: The regular expressio n a represents the language {a}.The regular expression ǫ represents the language {ǫ}.The regular expression ∅ represents the empty language.11Example: a∗(a ∪ b)a ∪ b represents the language {a } ∪ {b} = {a, b}.a∗represents {a}∗, the language containing strings wi t h 0 or more a’s: {ǫ, a, aa, aa a, aaaa, ...}.Concatenate these two languages: a∗(a∪b) represents the language containing all strings whichstart w i th some number of a’s, followed by either an a of b. Some strings in this language:aaaa, aaab, ab, b12Regular Expres sions: Operator PrecedenceOrder of operations (if unchanged by parentheses):1. ∗ (Kleene star operation)2. concatenation3. unionNotation: To distinguish between a regular expressio n R and the language it represents, wewill write L(R) for the language of R. However, we often blur the distinction.Example: What is t he language of each regular expression?1. ab∗a2. (0 ∪ 1)∗00(0 ∪ 1)∗3. 0∗1∗2∗4. a∗∅5. a(a ∪ b )∗∪ b(a ∪ b)∗b13Regular Expres sionsExample: Give a regular expression that generates the language.1. All bit strings that have a 0 as t he 5th symbol from the right.2. All strings over {a, b} having either aaa or bbb as a substring.3. All bit strings with length divisible by