1. Lecture # 4 Theory Of Automata By Dr. MM Alam
2. Lecture#3 Recap • Plus Operation Examples • Four way of defining languages • Examples for Descriptive way of defining languages
3. Recursive way A recursive definition is fundamentally a three- step process: • We specify some basic objects in the set. The number of basic objects specified must be finite. This means that we write some basic facts about the set • Second, we give a finite number of basic rules for constructing more objects in the set from the ones we already know. • Finally, we provide declaration that no objects
4. Language of Integer Defining language of INTEGER Rule 1: 1 is in INTEGER. Rule 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER. Rule 3: No strings except those constructed in above, are allowed to be in INTEGER.
5. • Defining the language L, of strings beginning and ending in different letters , defined over Σ={a, b} Rule 1: ab and ba are in L Rule 2: (a)s(b) and (b)s(a) are also in L, where s belongs to Σ* Rule 3: No strings except those constructed in above, are allowed to be in L
6. Factorial Example • Lets consider the language of factorial: Rule 1: We know that 0!=1, so 1 is in factorial. Rule 2: Also n!=n*(n-1)! is in factorial. Rule 3: Thus, no strings except those constructed in above, are allowed to be in factorial.
7. Consider the set P-EVEN, which is the set of positive even numbers. Method#1: We can define P-EVEN to be the set of all positive integers that are evenly divisible by 2. OR P-EVEN is the set of all 2n, where n = 1, 2, . . .. P-EVEN is defined by these three rules:
8. How to apply a recursive definition In particular, to show that 12 is in P-EVEN using the last definition, we would have to do the following: • 2 is in P-EVEN by Rule 1. • 2 + 2 = 4 is in P-EVEN by Rule 2. • 4 + 2 = 6 is in P-EVEN by Rule 2. • 6 + 2 = 8 is in P-EVEN by Rule 2. • 8 + 2 = 10 is in P-EVEN by Rule 2. • 10 + 2 = 12 is in P-EVEN by Rule 2.
9. Method#2 We can make another definition for P-EVEN as follows: Rule 1: 2 is in P-EVEN. Rule 2: If x and y are both in P-EVEN, then x + y is in P-EVEN. Rule 3: No number is in P-EVEN unless it can be produced by rules 1 and 2. How to show that 12 is in P-EVEN:
10. • Example: Let PALINDROME be the set of all strings over the alphabet = {a, b} PALINDROME = {w : w = reverse(w)} = {Λ, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, abba, . . .}. A recursive definition for PALINDROME is as follows: • Rule 1: , a, and b are in PALINDROME. • Rule 2: If w 2 PALINDROME, then so are awa and bwb. • Rule 3: No other string is in
11. Regular Expressions • Regular expressions is a common means of defining a language. It actually provide concise matching of string. • The concept is associated with the Kleenes formalism of regular sets introduced in 1950 • Useful operators used in the regular expression are as follows: * = 0 or more
12. a|b = a or 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
13. • Construct a regular expression for all words in which a appears tripled, if at all. This means that every clump of a’s contains 3 or 6 or 9 or 12... a’s • (aaa + b)* or (b + aaa)* or ((aaa)*b*)* or (b*(aaa)*)*
14. • Construct a regular expression for all words that contain at least one of the strings s1, s2, s3, or s4 • (s1 + s2 + s3 + s4)(s1 + s2 + s3 + s4)*
15. Lecture#4 Summary • Recursive way of defining languages • Recursive way examples • Regular expressions • Regular expression examples