Regular Expressions and Regular Languages - Hacettepe

Regular Expressions and Regular Languages

? Regular Expressions ? Converting Regular Expressions to NFA ? Converting Finite Automata to Regular

Expressions ? Algebraic Laws for Regular Expressions

BBM401 Automata Theory and Formal Languages

1

Regular Expressions

? We used Finite Automata to describe regular languages. ? We can also use regular expressions to describe regular languages.

? Regular Expressions are an algebraic way to describe languages. ? Regular Expressions describe exactly the regular languages. ? If E is a regular expression, then L(E) is the regular language that it defines. ? For each regular expression E, we can create a DFA A such that L(E) = L(A). ? For each a DFA A, we can create a regular expression E such that L(A) = L(E) ? A regular expression is built up of simpler regular expressions (using defining rules)

BBM401 Automata Theory and Formal Languages

2

Operations on Languages

? Remember: A language is a set of strings ? We can perform operations on languages.

Union: Concatenation: Powers: Kleene Closure:

L M = { w : w L or w M } L.M = { w : w=xy, x L, y M } L0 = { } , L1 = L , Lk+1 = L. Lk L* = = Li

BBM401 Automata Theory and Formal Languages

3

Operations on Languages - Examples

L = {00,11}

M = {1,01,11}

L M = {00,11,1,01}

L.M = {001,0001,0011,111,1101,1111}

L0 = {}

L1= L ={00,11} L2={0000,0011,1100,1111}

L*={, 00, 11, 0000, 0011, 1100, 1111, 000000, 000011, ...}

Kleene closures of all languages (except two of them) are infinite.

1. * = {}* = {} 2. {}* = {}

BBM401 Automata Theory and Formal Languages

4

Regular Expressions - Definition

Regular expressions over alphabet

Basis 1: Basis 2: Basis 3:

Reg. Expr. E a

Language it denotes L(E) { } {} {a}

Note: {a} is the language containing one string, and that string is of length 1.

BBM401 Automata Theory and Formal Languages

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download