Important concepts of RE and RD Semester Fall 2011 CS402Thoery of Automata

[Vuhelper]

for more detail look at on attachment


Important concepts of RE and RD
Semester: Fall 2010
CS402:Thoery of Automata

Q1. Show that the following is a recursive definition of the set EVEN = {2,4,6,…}

Rule 1 2 and 4 are in EVEN.
Rule 2 If x is in EVE, then so is x + 4.

. Since 2 belongs to EVEN so 2 + 4 = 6 belongs to EVEN
Since 4 belongs to EVEN so 4 + 4 = 8 belongs to EVEN
Since 6 belongs to EVEN so 6 + 4 = 10 belongs to EVEN
Since 8 belongs to EVEN so 8 + 4 = 12 belongs to EVEN

Hence Rule 1 and Rule 2 define the set EVEN recursively.

Q2. Show that the following pairs of regular expressions define the same language over the alphabet
 = {a, b}

(i) (ab)*a and a(ba)*
(ii) (a* + b)* and (a + b)*
(iii) (a* + b*)* and (a + b)*

i) (ab)* {, ab, abab, ababab, }
(ab)*a {a, aba, ababa, abababa, }
(ba)* {, ba, baba, bababa, }
a(ba)* {a, aba, ababa, abababa, }
Hence (ab)*a and a(ba)* define the same language.

ii) a* + b {b, , a, aa, aaa, }
(a*+ b)* {, a, b, aa, ab, ba, bb, }
(a + b)* {, a, b, aa, ab, ba, bb, }
Hence (a*+ b)* and (a + b)* define the same language.

iii) a* {, a, aa, aaa, }
b* {, b, bb, bbb, }
a* + b* {, a, b, aa, bb, aaa, bbb, }
(a* + b*)* {, a, b, aa, ab, ba, bb, }
(a + b)* {, a, b, aa, ab, ba, bb, }
Hence (a*+ b*)* and (a + b)* define the same language.

Q3. Give the recursive definition of language “number multiple of five” L={5, 10, 15, 20,……}

Step 1 : 5 is in L
Step 2 : If x is in L, then is x + 5
Step 3 : No strings except those constructed in above, are allowed to be in L.

Q4. Give regular expression of the language of all words of length 5, that starts and ends with same letter.
Answer:
a (a + b) (a + b) (a + b) a + b (a + b) (a + b) (a + b) b

Q5.Give Regular Expressions for the following languages (L1, L2, L3) defined over the alphabet {0, 1}
L1 = The set of strings in which every 0 is followed immediately by 11.
1*(011)*1*

L2 = The set of strings of 0's and 1's whose number of 0's is divisible by 5.
(1*01*01*01*01*01*)*

L3 = The set of strings of 0's and 1's whose 3rd symbol from the right is 1.
(0+1)*1(0+1)(0+1)





Q.6. Write the recursive definition of the language.

Defining the language {0n12n }, n=1,2,3,… , of strings defined over Σ={0,1}

Step 1: 011 is in {0n12n}.
Step 2: if x is in {0n12n}, then 0x11 is in {0n12n}.
Step 3: No strings except those constructed in above, are allowed to be in {0n12n}.

Q.7. Give regular expression to the following languages.
a) Language on the alphabet {0,1 } that have at least one “1”.
(0 + 1)* 1 (0 + 1)*

b) Language on the alphabet {0,1 } that have at most one “1”.
0* + 0* 1 0*

c) Of all words of length 6, that starts and ends with different letter.
a (a + b) (a + b) (a + b) (a + b) b + b (a + b) (a + b) (a + b) (a + b) a

Q.8. Write down the RE of following languages defined over Σ = {a,b}:

2.1) Language L with Strings having “aba” anywhere in them
RE: (a+b)*aba(a+b)*

2.2) Language L with Strings, starting and ending with “aba”
RE: aba(a+b)*aba

Q.9. Following alphabet are valid or invalid.
a)
i) Σ= {cd, ef, c} Invalid.
ii) Σ= {aB, D, A} Valid.
b) What is the length of the following string defined over alphabet Σ= {aB, D, A}?
aBaBAaBD length of string is 5

Exercise for students
Question No.1

a) Give regular expressions of the following languages over Σ={0,1}:
1. All strings having no pair of consecutive zeros.
2. All strings having exactly two 1’s or three 1’s not more than it.
b) Show that the Regular expression ^ + 0(0+1)*+(0+1)*00(0+1)* is equivalent to ((0*1)*01*)*

Question No. 2

a) Give recursive definition for the language ODD, of strings defined over ∑={-,0,1,2,3,4,5,6,7,8,9},
b) Give recursive definition for the language of palindromes having odd length

Question No. 3
Write RE of the language defining over Σ={a, b} that accepts only those words that do not contain the substring “ba”.


Wish u GOOD LUCK

for more detail look at on attachment