Scribd
Upload
99 views

Theory of Automata

This document discusses theory of automata and regular expressions. It defines concatenation of strings and languages, union of strings, and provides examples of converting strings to regular expressions. Regular expressions are used to define languages containing certain substrings or with constraints on string length or alphabet occurrences. Examples are provided to illustrate regular expressions for languages matching given criteria.

Uploaded by

Fatima
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
99 views

Theory of Automata

This document discusses theory of automata and regular expressions. It defines concatenation of strings and languages, union of strings, and provides examples of converting strings to regular expressions. Regular expressions are used to define languages containing certain substrings or with constraints on string length or alphabet occurrences. Examples are provided to illustrate regular expressions for languages matching given criteria.

Uploaded by

Fatima
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 22

Theory Of Automata

1
Lecture # 06
Theory of Automata

2
Revision
 Concatenation of strings
 Language Concatenation
 Union of strings
 Regular expressions
 Conversion of string in to Regular

expressions
 Examples of RE

3
1:Concatenation of Strings
 ◦ is the concatenation operator

 Example:
Suppose w1 and w2 are two strings
w1 = abc, w2 = def
w1 ◦ w2 = abcdef
w2 ◦ w1 = defabc
w2 ◦ w2 = defdef

 Often drop the ◦: w1w2 = abcdef


 For any string w, w €= w [€ = empty string]
4
We can concatenate a string with itself:
w1 = w
w2 = ww
w3 = www

 By definition, w0 = €

Can reverse a string: wR


abcdeR = edcba

5
Language Concatenation
 We can concatenate languages as well as
strings
 L1L2 = {wv : w ∈ L1 ∧ v ∈ L2}
 Example:

{a, ab}{bb, b} = {abb, ab, abbb}


{a, ab}{a, ab} = ?
{a, aa}{a, aa} = ?

 What can we say about |L1L2|, if we know |


L1| = m and |L2| = n?

6
 We can concatenate a language with itself,
just like
 strings
 L1 = L, L2 = LL, L3 = LLL, etc.

 What should L0 be, and why?

7
L0 = {€}
{} is the empty language
{€} is the trivial language

 Kleene Closure (L)


L* = L0 ∪ L1 ∪ L2 ∪ L3 ∪ . . .

8
2: Union of Strings
Use of OR (+) operator for regular expression:

 a|b = a or b = (a+b) = {a,b} = {a} U {b}


 (a|b)* = (a or b) 0 or more times
 (a|b)+ = (a or b) 1 or more times
 a|b* = a or b (only b 0 or more times)
 (a|b)*(c|Λ) = (a or b) 0 or more times and c
or Null string

 Note: {a,b} is not a R.E

10
Conversion of strings into Regular
Expressions
 Convert the following into a Regular
Expression.

1: {a,bc} = (a +bc )
2: {1,11,111,1111,……} = 1(1)*
3: {a,ab,b,bb} = (a+ab+b+bb)
= a(1+b) b(1+b)

4: {a,ab,abb,abbb,abbbb,……..} =ab*

11
Regular Expression Examples
Expand the following R.E.

1: (a+b)* = {Λ,a,b,aa,ab,ba,bb,aaa,aab,aba,…}

2: (a.b)* = {ab,abab,ababab,…….}

3: ((a*).(b*)) = {Λ,a,b,aa,ab,bb,aaa,aab,abb,
bbb,...}

12
4: ((a+b)(b*)) =
{a,b,ab,bb,abb,bbb,abbb,bbbb,….}

5: (( (a+b)(b*))a) = {aa,ba,aba,bba,abba,bbba,
….}

6: (a( (a+b)*)a) =
{aa,aaa,aba,aaaa,aaba,abaa,abba,…….}

13
 Define a Regular expression for language that
contains all of the strings of a and b

 L= {a,b,aa,ab,ba,bb,aaa,aab,aba,abb,bbb,….}
 For the above strings the RE will be
 (a+b)*

14
 Define a Regular expression for language that
contains substring ba

 L= {abaa,abab,bbaa,bbab,aabaa,abbaa….}
 For the above strings the RE will be
 (a+b)* ba (a+b)*

15
 Define RE for all strings which don’t contain
substring ba .

 For the above strings the RE will be


 b* . a*

 Define RE for all strings which starts with an a.


 L= {a,aa,ab,aaa,aab,aba,abb,aaaa,……..}
 For the above strings the RE will be
 a(a+b)*

16
 Define RE for all strings over alphabet {a,b}
that are even in length.
 L= {Λ ,aa,ab,ba,bb,aaaa,bbbb,…..}
 R.E = ((a+b)(a+b))*

 Define RE for all strings over alphabet {0,1}


that have an even number of 1’s
 L= {Λ ,

0,011,0101,01010,0011,00101,001010,….}
 R.E = 0*(10*10*)*

17
 Define R.E for all strings over a,b that starts
and end with same letter
 R.E = a(a+b)a + b(a+b)b

 Define R.E for a language that contains 00 as


a substring
 R.E = (0+1)* 00 (0+1)*

18
 Define a R.E for a language with set of all
strings ending with abb
 R.E = (a+b)* abb

 Define a R.E for a language with set of all


strings ending with either 010 or 0011
 R.E = (0+1)*.(010+0011)

19
 Define R.E for all strings having even number
of 0’s
 R.E = (00)*

 Define R.E for a language that contains


 odd numeber of 0’s
 R.E = 0.(00)*

20
 Define a R.E for a language with set of all
strings over an alphabet a b and c having
exactly one a .
 R.E = (b+c)* . a .(b+c)*

 Define a R.E for a language of all possible


strings whose length is 3 over alphabet a and
b
 R.E = (a+b)(a+b)(a+b)

21
Lecture Summary

 Examples of R.E

22

You might also like