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

[Vuhelper]

View more random threads:

• Solved paper MGT301 Principles of Marketing Fall 2009
• ENG201 Business and Technical English solve MIDTERM...
• It430 solved subjective past papers by vuhelp
• MGT201 Financial Management current mid term paper 12 May...
• eco401 mid term solve paper 2011 virtual university of...
• Important concepts of RE and RD Semester Fall 2011...
• Solved Paper FIN622 Final Term Fall 2009
• Mkt50marketingmanagement1 midterm solved papers fall 2010
• MGT201 Financial Management all solved mcqs and papers fall...
• cs403 full solve paper fall 2011-2012 virtual university of...

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)



Sponsored Links



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