1. Why regular expressions

What are regular expressions for?

Regular expressions are used whenever a task requires pattern matching:

• search engines
• protein analysis (bioinformatics)
• search and replace in text editors
• text processing utilities such as sed and awk

Many programming languages provide various regular expression capabiltiies. Lexical analysers in compilers also use regular expressions.

Finite representation of languages

Consider the following language:

$$\begin{array}{r}L=\text{all strings of }\alpha \text{ and }\beta \text{ that have two or three occurrences of }\beta ,\\ \text{ the first and second of which are not consecutive}\end{array}$$

Can we describe this infinite language with a finite pattern?

• Strings in $L$ can start with any number (possibly none) of $\alpha$: ${\alpha }^{\ast }$

• Then we have the first $\beta$, it should be alone and followed by at least one $\alpha$: $\beta \alpha$

• Then any number (possibly none) of $\alpha$: ${\alpha }^{\ast }$

• Then comes the second $\beta$: $\beta$

• Then either:

  • No more $\beta$ but can be any number (possible none) of $\alpha$.
  • Or after some (possibly none) $\alpha$, there is a third $\beta$ somewhere, followed by any number (possibly none) $\alpha$.

  This gives us: ${\alpha }^{\ast }\cup {\alpha }^{\ast }\beta {\alpha }^{\ast }$

Combining all of these together gives us:

$${\alpha }^{\ast }\beta \alpha {\alpha }^{\ast }\beta ({\alpha }^{\ast }\cup {\alpha }^{\ast }\beta {\alpha }^{\ast })⇝\underline{\text{ regular expression }}\text{ representing }L$$Link to original

2. Examples of regular expressions

Example 2

Given the following language:

$$\begin{array}{rl}L& =\text{all the strings consisting of some number (possibly none)}\\ & \text{ of }a\text{ followed by some number (possibly none) of }b\\ & =\{ϵ,a,b,aa,bb,ab,aaa,aab,bbb,abb,abb,...,aaaabbbbbbb\}\end{array}$$

We can use the regular expression:

$$a^{\ast }{b}^{\ast }⇝L\text{ is represented by the regular expression }{a}^{\ast }{b}^{\ast }$$

We use the notation: $\boxed{L=\text{Language\_of}(a^{\ast }{b}^{\ast })}$ Which we read as “the language of $a^{\ast }{b}^{\ast }$ is $L$”, or “the language represented by $a^{\ast }{b}^{\ast }$ is $L$”.

Example 3

$$\begin{array}{rl}\text{Langauge\_of}(a(a^{\ast }\cup b^{\ast }))& =\text{all words starting with }a\text{ followed by either a}\\ & \text{(possibly empty) word of }a\text{ or a (possibly empty)}\\ & \text{word of }b\\ & =\{a,aa,ab,aaa,abb,aaaa,abbb,aaaaaa,abbbbbbb\}\end{array}$$

Example 4

$$\begin{array}{rl}\text{Language\_of}(a(a\cup b^{\ast }))& =\text{all words starting with }a\text{ followed by}\\ & \text{any word over }\{a,b\}\\ & =\text{all words over }\{a,b\}\text{ starting with }a\\ & =\{a,aa,ab,aaa,aab,aba,abb,aaaaa\}\end{array}$$

Example 5

Find the $\text{Language\_of}((b\cup aa{a}^{\ast })\ast )$.

1. Start by finding $\text{Language\_of}(aa{a}^{\ast })$

   $$\begin{array}{rl}\text{Language\_of}(aa{a}^{\ast })& =\text{all words of }a\text{ of length }\ge 2\\ & =\{aa,aaa,aaaa,aaaaa,...\}\end{array}$$

2. Find $\text{Language\_of}(b\cup aa{a}^{\ast })$

   $$\begin{array}{rl}\text{Language\_of}(b\cup aa{a}^{\ast })& =\text{ as above plus the word }b\\ & =\{b,aa,aaa,aaaa,...\}\end{array}$$

3. Find $\text{Language\_of}((b\cup aa{a}^{\ast })\ast )$ We can take any number (possibly none) of words from $\text{Language\_of}(b\cup aa{a}^{\ast })$ and concatenate them together.

Example 6

Find the $\text{Language\_of}((b\cup a)a{a}^{\ast })$.

1. Find $\text{Language\_of}(b\vee a)=\{a,b\}$.
2. Find $\text{Language\_of}((b\vee a)a)=\{aa,ba\}$.
3. Find $\text{Language\_of}((b\vee a)aa\ast )=$ all words starting with $aa$ or $ba$ followed by a (possibly empty) word of $a$s.

Example 7

Find the $\text{Language\_of}(ϵ\vee c^{\ast }(a\vee b{c}^{\ast }))$

All the strings that are either empty or start with some (possibly none) $c$s followed by either an $a$, or a $b$ followed by (possibly none) $c$s.

For example, $\{ϵ,a,b,be,bee,ca,cb,cbc\}$.

Link to original

3. Describing regular expressions by recursion

Describing regular expressions by recursion

Regular expression

A regular expression (over alphabet $S$) is a string consisting of:

• symbols from $S$
• and symbols from $\cup ,{}^{\ast },(,),ϵ,\varnothing$.

Link to original

The infinite set of regular expression over $S$ is defined recursively as follows:

• Basis case: $\varnothing$, $ϵ$, and each symbol in the alphabet $S$ are regular expressions.
• Recursive step: if $R$ and $Z$ are regular expressions, then so are $(R\cup Z)$, $(RZ)$, and $(R^{\ast })$.

Notational conventions

There are some conventions to follow when working with regular expressions:

• Outermost brackets are omitted.
• Brackets are omitted when concatenating expressions. e.g. writing $abaab$ instead of $(((ab)(ab))b)$.
• ‘binds’ take precedence over concatenation e.g. we write $aa{b}^{\ast }$ instead of $(aa)(b^{\ast })$

Link to original

4. Regular languages

Regular languages

Each regular expression over some alphabet $S$ represents a language over $S$.

The following are two different things:

• A regular expression $R$. A string or finite pattern.
• The language $R$ represents: $\text{Language\_of}(R)$. A set of words over $S$, words following the pattern.

Regular Language

A regular language is any language that can be representeed by a regular expression. A language $L$ is regular if $L=\text{Language\_of}(R)$ for some regular expression $R$.

Link to original

To compare:

• A regular expression is a pattern.
• A regular language is a set of words following a pattern.

Recursive description

The recursive description of the language $\boxed{\text{Language\_of}(R)}$ represented by the regular expression $R$ is:

• Basis Case: $$\begin{array}{rl}\text{Language\_of}(\varnothing )& =\varnothing \\ \text{Language\_of}(ϵ)& =ϵ\\ \text{Language\_of}(a)& =a\text{ for any symbol }a\text{ in the alphabet }S\end{array}$$
• Recursive Step: If $R$ and $Z$ are regular expression, then:
  • $\text{Language\_of}(R\cup Z)=$ all words that belong either to $\text{Language\_of}(R)$ or to $\text{Language\_of}(Z)$.
  • $\text{Language\_of}(RZ)=$ any words from $\text{Language\_of}(R)$ followed by any word from $\text{Language\_of}(Z)$
  • $\text{Language\_of}(R^{\ast })=$ any word from $\text{Language\_of}(R)$ followed by any word from $\text{Language\_of}(R)$ … (the number of iterations is arbitrary, possibly none)

Link to original

5-6. Turning regular expressions to NFAs

Turning regular expressions to NFAs

1. There is a general ‘mechanical’ proecedure ${\mathcal{P}}_1$ that converts any regular expression $R$ to an NFA $A_R$ such that $L(A_R)=\text{Language\_of}(R)$. So every regular language is accepted by some automaton.
2. There is a general ‘mechanical’ procedure ${\mathcal{P}}_2$ that converts any NFA $A$ to a regular expression $R_A$ such that $\text{Language\_of}(R_A)=L(a)$. So every language that is accepted by some automaton is regular. This algorithm is out of scope.

title: Regular langauges are <u>precisely those</u> languages that are accepted by finite automata.

Procedure ${\mathcal{P}}_1$

The procedure $P_1$ which converts any regular expression $R$ to an NFA $A_R$ such that $L(A_R)=\text{Language\_of}(R)$ operates along the recursive description of the regular expression $R$.

Basis Cases

• If $R=\varnothing$ then $\text{Language\_of}(R)=\varnothing$.

  digraph {
    rankdir=LR
    init[shape=point]
    node[label="" shape=doublecircle];
    node[shape=circle];
    init->s
  }

• If $R=ϵ$ then $\text{Language\_of}(R)=ϵ$.

  digraph {
    rankdir=LR
    init[shape=point]
    node[label="" shape=doublecircle color=purple] s;
    node[shape=circle];
    init->s
  }

• If $R=a$ then $\text{Language\_of}(R)=a$.

  digraph {
    rankdir=LR
    init[shape=point]
    node[label="" shape=doublecircle color=purple] a;
    node[shape=circle color=""] s;
    init->s
    
    s->a [label=a]
  }

Assumptions for recursive cases

• $\boxed{A_R}$: accepts $\text{Language\_of}(R)$

• $\boxed{A_Z}$: accepts $\text{Language\_of}(Z)$

  digraph {
    subgraph cluster0 {
    	label="R"
    	init[shape=point]
    	node[label="" shape=doublecircle color=purple] a, b;
    	node[shape=circle color=""] s, c, d;
    	init->s
    }
    
    subgraph cluster1 {
    	label="Z"
    	init2[shape=point]
    	node[label="" shape=doublecircle color=purple] f, g;
    	node[shape=circle color=""] e, h, i;
    	init2->e
    }
  }

Recursive Cases: Automaton accepting $\text{Language\_of}(R\cup Z)$ (accepted by $A_{R\cup Z}$)

digraph {
	node[label=""]
	
	init[shape=point]
		
	init->z
	z->s [label=ε]
	z->e [label=ε]
 
	subgraph cluster0 {
		label="R"
		node[label="" shape=doublecircle color=purple] a, b;
		node[shape=circle color=""] s, c, d;
	}
 
	subgraph cluster1 {
		label="Z"
		node[label="" shape=doublecircle color=purple] f, g;
		node[shape=circle color=""] e, h, i;
	}
}

Recursive Cases: Automaton accepting $\text{Language\_of}(RZ)$ (accepted by $A_{RZ}$)

digraph {
  node[label=""]
 
  subgraph cluster1 {
  	label="Z"
  	node[label="" shape=doublecircle color=purple] f, g;
  	node[shape=circle color=""] e, h, i;
  }
  
  subgraph cluster0 {
  	label="R"
  	init[shape=point]
  	node[shape=circle color=""] s, c, d;
  	init->s
  	a->e [label=ε];
  	b->e [label=ε];
  }
}

Recursive Cases: Automaton accepting $\text{Language\_of}(R^{\ast })$ (accepted by $A_{R^{\ast }}$)

digraph {
  init[shape=point];
  	
  node[label="" shape=doublecircle color=purple] w;
  init->w
  
  node[shape=circle color=""]
  w->s
  a->w
  b->w
  	
  subgraph cluster0 {
  	label="R"
  	node[shape=circle color=""] a, b, s, c, d;
  }
}

Link to original

7. Regex to NFA Example 1

Example 1

Apply the proecdure to the regular expression $((a\cup ab{)}^{\ast }ba{)}^{\ast }$. We construct step-by-step an NFA $A$ such that:

$$L(A)=\text{Language\_of}(((a\cup ab{)}^{\ast }ba{)}^{\ast })$$

Step $0$: automata accepting $\text{Language\_of}(a)$ and $\text{Language\_of}(b)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] a;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=a]
}
 
digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] a;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=b]
}

Step $1$: automata accepting $\text{Language\_of}(ab)$ and $\text{Language\_of}(ba)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] b;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=a]
	a->b [label=b]
}

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] b;
	node[shape=circle color=""] s;
	init->s
 
	s->a [label=b]
	a->b [label=a]
}

Step $2$: automaton accepting $\text{Language\_of}(a\cup ab)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] b,j;
	node[shape=circle color=""] s;
	init->g
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
}

Step $3$: automaton accepting $\text{Language\_of}((a\cup ab{)}^{\ast })$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] k;
	node[shape=circle color=""] s;
	init->k
 
	k->g [label=ε]
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
	
	b->k [label=ε]
	j->k [label=ε]
}

Step $4$: automaton accepting $\text{Language\_of}((a\cup ab{)}^{\ast }ba)$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] m;
	node[shape=circle color=""] s;
	init->k
 
	k->g [label=ε]
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
	
	b->k [label=ε]
	j->k [label=ε]
	
	k->n [label=b]
	n->m [label=a]
}

Step $5$: automaton accepting $\text{Language\_of}(((a\cup ab{)}^{\ast }ba{)}^{\ast })$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle color=purple] m;
	node[shape=circle color=""] s;
	init->k
 
	k->g [label=ε]
 
	s->a [label=a]
	a->b [label=b]
	
	g->s [label=ε]
	g->h [label=ε]
	h->j [label=a]
	
	b->k [label=ε]
	j->k [label=ε]
	
	k->n [label=b]
	n->m [label=a]
}

Link to original

8. Regex to NFA Example 2

Example 2

Construct an automaton accepting $\text{Langauge\_of}(a^{\ast }(b\cup ab{)}^{\ast }b{b}^{\ast })$

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; f;
	node[shape=circle];
	init->a
	
	a->a [label=a]
	a->b [label=ε]
	b->c [label=ε]
	c->d [label=a]
	d->e [label=b]
	e->b [label=ε]
	b->f [label=b]
	f->f [label=b]
	c->g [label=b]
	g->b [label=ε]
}

Link to original

9. Example of nonregular language

Example of nonregular language

Consider the following language over the alphabet $\{a,b\}$:

$$\begin{array}{rl}L& =\text{all words starting with a word of }a\text{’s followed}\\ & \text{by an equal-length word of }b\text{’s}\\ & =\{a^n{b}^n|n=0,1,2,...\}\end{array}$$

Suppose that a finite automaton $A$ tries to recongise words in this language. Then $A$ must store the entire sequence of $a$‘s before the first $b$ shows up. Otherwise $A$ will not be able to compare the length of the coming word of $b$s with the length of the prefix of $a$s.

As each automaton is capable for a fixed finite amount of storage with the help of its states, no automaton $A$ exists such that $L(A)=L$.

There is a precise mathematical proof justifying this informal argument: this language $L$ is indeed not regular.

Link to original