Regular Languages


Date: 2021-02-04


title: 'Regular Languages' date: '2021-02-04'

Regular Languages

Deterministic Finite Automata

Def: be a deterministic finite automata, and let be a string where . accepts if a sequence of states in Q exists with 3 conditions:

  1. (starts in start state)
  2. (state transition according to ) for
  3. (input ends in accept state)

recognizes language if .

Def: A language is called regular language if some finite automaton recognizes it.

Design Finite Automata

3 Operations on Languages (Closed under regular operations)

Let be languages,

  • Union:
  • Concatenation:
  • Star:
    • Empty string is always in a member of

Closed under Operations are regular is regular Proof: Let recognizes , recognizes . Construct to recognize .

  • Union of two alphabets (true if two are different)

are regular is regular Proof needs Nonderminism to break input into two pieces

Nonderminism

Def: is a nondeterministic finite automata, where

  1. is finite set of states
  2. is a finite alphabet
  3. is the transition function
  4. is the start state
  5. is the end state

Differences bewteen DFA:

  • For one single input, transition funciton of NFA can have zero, one or multiple output states
  • transition: transition without reading any input
  • The machine splits into multiple copies of itself and follows all the possibilities in parallel. Finally, if any one of these copies of the machine is in an accept state at the end of the input, the NFA accepts the input string.

Think about Nonderminism computation as a tree of all possibilities

Equivalence between NFAs and DFAs Two machines are equivalent if they recognize the same language. Let be the NFA recognizing the same language, construct the DFA counterpart by construction: Proof:

  • For and , let , aka:

To take transition into account, Definition: Missing close braceE(R) = \{q | q \text{ can be reached from RExtra close brace or missing open brace by traveling along 0 or more } \varepsilon\}. Modify by incorporating : And

Corollary A language is regular if and only if some nondeterministic finite automaton recognizes it, for

  1. NFA DFA equivalence
  2. A language is regular if and only if it is recognized by a DFA

###Closed under Operations recognizes , and recognizes . Closed under union Construct to recognize

  2. special start state that has arrows to and

Note: Think about the new NFA as the root with two children and

Closed under concatenation Construct to recognize

Note: Think about concatenation of two linked lists by connecting final state(s) of and by transition

Closed under star operation is recognized by NFA , construct to recognize

  2. is the new start state that which is the old start state
  3. accepts both the new and old start state

Regular Expression

is a regular expression if is:

  2. empty string
  3. empty language : doesn't contain any string
  4. , where are regular expression
  5. , where are regular expression
  6. , where is regular expression

Note:

  • . Concatenating the empty set to any set yields the empty set
  • . Empty string is always in a member of . If the language is empty, the star operation can put together 0 strings, giving only the empty string.

Equivalence with Finite Automata

Theorem: A language is regular if and only if some regular expression describes it. Lemma If a language is described by a regular expression, then it is regular. Proof: describes language . Let's convert into an NFA . Consider six cases in regular expression:

  1. where and for

  2. empty string where for any

  3. empty language : doesn't contain any string where for any (Cases below are closed under operations)

  4. , where are regular expression

  5. , where are regular expression

  6. , where is regular expression

Lemma If a language is regular (a NFA that recognizes it), then it is described by a regular expression. Proof: If a language is regular, it is recognized by a DFA. Convert the DFA into equivalent regular expression. A new type of finite automata is needed: generalized nondeterministic finite automata (GNFA): NFA where transition arrows may have regular expression as labels.

Idea: Convert the GNFA with states to an equivalent GNFA with states, call the state removed . In the old machine, if

Then in the new machine, This machine recognizes the original language.

Formally, where

  1. is finite states
  2. is the input alphabet

is the collection of all regular expressions over . If , the arrow from to has the regular expression R as its label

  1. is the start state
  2. is the accept state

accepts a string if each and a sequence of state exists such that

  3. for each , , where

Proof: ...

Nonregular Languages

Pumping lemma

If is a regular language, then there is a number (pumping length) where if is any string in of length at least , then may be divided into three pieces, where

  1. for each ,

Idea: take a string of at least . If length of is , then the sequence of states has length . By pigeonhole principle, there must be a state that is repeated.

Pumping lemma practice

Let , y comprises of a only.

Let . Since , and , Contradiction: no whole number between and

Pumping down: Let , y comprises of 0 only. . contradiction.

© 2022 Yuk Yeung Lam. All Rights Reserved.