Automata 05

Regular languages

Closure under operation definition

For example is closed under addition and multiplication, but not subtraction And is closed under addition, multiplication and subtraction, but not division

Closure of a set of regular languages

List of operations under which closure is preserved, proofs are below

• Complement
• Union
• Intersection
• Concatenation
• Kleene closure
• Reverse
• Prefix

Closure under concatenation lemma

Closure under Kleene closure lemma

Clearly, a finite number of operation compositions preserves the closure. From this follows that any finite language is regular(!)

Closure under reverse lemma

Closure under prefix lemma

---

Regular expressions (regex) definition

Regular expression is a short(er) way to express a set of strings

A formal inductive definition is as follows:

Each regular expression can be represented by a tree, and represents a regular language

In regular expressions, the following order (priority) of operations is established:

• Parentheses (grouping)
• Asterisk (Kleene closure)
• Concatenation
• Union
• left-to-right

Representing a regular language as a regular expression

Exercises

All exercises assume

Generalized non-deterministic finite automaton (GFA or GNFA)

A generalized non-deterministic finite automaton is different from NFA in the following way:

Equivalence of GNFA and DFA theorem

Equivalence of regular language and a regular expression theorem

---

Pumping lemma lemma

Example

Example

Example

Example

Example

Example

Example

---

Using closure properties to determine regularity

Example

Example

Example