ݺߣ

ݺߣShare a Scribd company logo

PART A.doc

?Download as DOC, PDF?
?
karthikeyan Muthusamy
karthikeyan Muthusamy

This document discusses regular expressions and regular languages. It covers topics like regular expressions, regular languages, pumping lemma, closure properties of regular languages, and equivalence of finite automata and regular expressions. It also lists important questions related to this unit from previous years' question papers. These questions cover regular expressions, pumping lemma, closure properties, equivalence of finite automata and regular expressions, and proving languages to be non-regular. The document provides solutions to some of these questions as examples.

1 of 10
UNIT - II REGULAR EXPRESSIONS AND LANGUAGES ? Regular expression ? Regular Languages ? Equivalence of Finite Automata and regular expressions ? Proving languages to be not regular (Pumping Lemma) ? Closure properties of regular languages.
LIST OF IMPORTANT QUESTIONS UNIT - II REGULAR EXPRESSIONS AND LANGUAGES PART C A 1. Show whether the language L = {0n12n | n > 0} is regular or not using pumping lemma (April/May 2017) 2. What are the closure properties of regular languages? (Nov/Dec 2016) (May/June2014), (May/June2013) 3. State the pumping lemma for Regular Languages. (May/June 2016)(Nov/Dec 2014)(Nov/Dec 2013) 4. Write Regular Expression for the set of strings over {0,1} that have atleast one.(Nov/Dec 2015) 5. What is a regular expression? (May/June2013) PART B 1) Find the regular expression of a language that consists of set of string starts with 11 as well as ends with 00 using Rij formula. (April/May2015) 2) Discuss the closure properties of regular languages. (Nov/Dec2013) (May/June2013) (Or)Prove that the class of regular sets is closed under complementation. (May/June2014) 3) Prove that A Language L is accepted by some DFA if and only if L is accepted by some NFA. (or) Let L be set accepted by a NFA and then prove that there exists a DFA that accepts L. (Nov/Dec2015) (Nov/Dec2014) (Nov/Dec2013) 4) Discuss on regular Expression. Write a regular expression for set of strings that consist of alternating 0s and 1s. (May/June 2016) (May/June2013) ii) Prove that the following languages are not regular. (May/June2013) 1) {02n | n > 1} 2) {ambnam+n | m > 1 and n > 1} (or) L = { 0m1n0m+n | m > 1 and n > 1} (Nov/Dec2013)
UNIT - II REGULAR EXPRESSIONS AND LANGUAGES PART A 1) Show whether the language L = {0n12n | n > 0} is regular or not using pumping lemma(April/May 2017) SOLUTION: The number of states is 3n > n. w = 0n12n The length of the string |w| = 3n > n Assume xy = 0m, y = 0j , z = 0n-m . 12n xykz = xy(y)k-1z = 0m . 0j(k-1) . 0n-m . 12n xykz = 0n + j(k-1) . 12n Apply k = 0 xykz = 0n - j. 12n L Apply k = 1 xykz = 0n . 12n L Apply k = 2 xykz = 0n + j. 12n L
Thus the Language L = {0n12n | n > 0} is not a regular Language 2) What are the closure properties of regular languages? (Nov/Dec 2016) (May/June2014), (May/June2013) CLOSURE PROPERTIES OF REGULAR LANGUAGES The regular languages are closed under i. The union of two regular languages is regular. ii. The intersection of two regular languages is regular. iii. The complement of two regular languages is regular. iv. The difference of two regular languages is regular. v. The reversal of regular languages is regular. vi. The closure of regular languages is regular. vii. The concatenation of regular languages is regular. viii.The homomorphism of regular languages is regular. ix. The inverse Homomorphism of regular languages is regular. 3) State the pumping lemma for Regular Languages (May/June 2016)(Nov/Dec 2014)(Nov/Dec 2013) PUMPING LEMMA: Let L be a regular languages. Then there exists a constant n such that for every string w in L such that |w| n. w=xyz such that i. y ii. |xy| n iii. for all i 0, xy iz L. 4) Write Regular Expression for the set of strings over {0, 1} that have atleast one. (Nov/Dec 2015) REGULAR EXPRESSION OF STRINGS {0, 1}: 1(0 + 1)* . 5) Define the term epsilon transition.[May/Jun 13] a. The is a character used to indicate null string.
b. i.e. the string which is used simply for transition from one state to other state without any input. 6) Define the language accepted by a NFA a. We define the language of a NFA A = (Q,, ,q0,F) by b. L(A) = { w|(q0,w) F }. 7) Define the language accepted by a DFA a. We define the language of a DFA A = (Q,, ,q0,F)by b. L(A) = { w|(q0,w) is in F}. 8) Differentiate L* and L+ a. L* denotes Kleene closure and is given by L* = U Li i=0 b. example: 0* ={ ?,0,00,000, } c. Language includes empty words also. d. L+ denotes Positive closure and is given by L+= U Li i=1 9) Define Substring. A string v appears within another string w(w=uv) is called substring of w. IF w=uv, then substrings u & v are said to be prefix and suffix of w respectively 10) What is a regular expression? (May/June2013) The Language accepted by finite automata are easily described by simple expression called regular expression. A regular expression is a string that describes the whole set of strings according to certain syntax rules. These expressions are used by many text editors and utilities to search bodies of text for certain patterns etc. Let be an alphabet. The regular expression over and the sets they denote are: i. is a R.E, denotes empty set and Language L() = { }. ii. pie is a R.E denotes the set { } and Language L(pie) = { pie}. iii. A variable represented in upper case like L is any language. iv.For each a in , a is a R.E and denotes the set {a}. v. If r and s are regular expression, then i. If r and s are R.E denoting the languages R and S respectively then (r+s), ii. (rs) and (r*) are R.E that denote the sets RUS, RS and R* respectively. 11)Write a r.e to denote a language L which accepts all the strings which begin or end with either 00 or 11.
The r.e consists of two parts: L1=(00+11) (any no of 0s and 1s) =(00+11)(0+1)* L2=(any no of 0s and 1s)(00+11) =(0+1)*(00+11) Hence r.e R=L1+L2 =[(00+11)(0+1)*] + [(0+1)* (00+11)] 12)Construct a r.e for the language over the set ={a,b} in which total number of as are divisible by 3 ( b* a b* a b* a b*)* 13)What is: (i) (0+1)* (ii)(01)* (iii)(0+1) (iv)(0+1)+ [Remember] (0+1)*= { ?, 0 , 1 , 01 , 10 ,001 ,101 ,101001, } Any combinations of 0s and 1s. (01)*={ ?, 01 ,0101 ,010101 , } All combinations with the pattern 01. (0+1)= 0 or 1,No other possibilities. (0+1)+= {0,1,01,10,1000,0101,.} 14)Reg exp denoting a language over ={1} having (i) even length of string (ii) odd length of a string. i. Even length of string R=(11)* ii. Odd length of the string R=1(11)* 15)Reg exp for: (i) All strings over {0,1} with the substring 0101 (ii) All strings beginning with 11 and ending with ab (iii) Set of all strings over {a,b}with 3 consecutive bs. (iv) Set of all strings that end with 1and has no substring 00 i. (0+1)* 0101(0+1)* ii. 11(1+a+b)* ab iii. (a+b)* bbb (a+b)* iv. (1+01)* (10+11)* 1 16)Construct a r.e for the language which accepts all strings with atleast two cs over the set ={c,b} (b+c)* c (b+c)* c (b+c)* 17)What are the applications of Regular expressions and Finite automata [Remember] a. Lexical analyzers and Text editors are two applications. Lexical analyzers: b. The tokensof the programminglanguage can be expressed using regular expressions.
c. The lexical analyzer scans the input program and separates the tokens.For eg identifier can be expressed as a regular expression d. as: (letter)(letter+digit)* e. If anything in the source language matches with this reg exp then it is recognized as an identifier.The letter is{A,B,C,..Z,a,b,c.z} and digit is {0,1,9}.Thus reg exp identifies token in a language. f. Text editors: g. These are programs used for processing the text. For example UNIX text editors uses the reg exp for substituting the strings such as: S/bbb*/b/ h. Gives the substitute a single blank for the first string of two or more blanks in a given line. In UNIX text editors any reg exp is converted to an NFA with ?transitions, this NFA can be then simulated directly.
18)Reg exp for the language that accepts all strings in which a appears tripled over the set ={a} [Apply] 19)reg exp=(aaa)* 20)Reg exp for the language such that every string will have atleast one a followed by atleast one b. [Apply] 21)R=a+b+ 22)Write the exp for the language starting with and has no consecutive bs. [Apply] 23)reg exp=(a+ab)* 24)Construct a regular expression denoting odd numbers in their binary representation. [Apply] 25){0/1}*1 26)Construct a regular expression denoting even numbers in their binary representation. [Apply] 27){0/1}*0 28)Construct a regular expression denoting the set of all strings of 0 and 1 beginning with 0 and ending with 1 . [Apply] [Nov 2012] 29)0{0/1}*1 30)Construct a regular expression denoting the set of all strings over {a,b} such that all starts with a and ends with ab. [Apply] 31)a{a/b}*ab 32)Construct a regular expression denoting the set of all strings of 0 and 1 ending in 00 . [Apply] [Nov 2012] 33){0/1}*00 34)Write the regular expression for set of all strings over {0,1} that have at least one. [Apply] (Nov / Dec 2015) 35)R=(0+1)*1(0+1)* 36)Construct a regular expression denoting the set of all strings over {a,b} such that all contains three as. [Apply] 37)b*ab*ab*ab* 38)What does the following regular expression denote 0*1*2*[Analyze] 39)The set of all words over {0,1} such that all starts with 0 number of 0s or 1 0s or more number of 0s followed by similar patterns of 1s and 2s. 40)Construct a regular expression for the set of strings that consist alternate 0s and 1s. [Apply] 41)(01)* + (10)*+ 0(10)* + 1(01)*
42)What are the applications of pumping lemma? [Remember] Pumping lemma is used to check if a language is regular or not. (i).Assume that the language(L) is regular. 43)(ii).Select a constant n. 44)(iii).Select a string(z) in L, such that |z|>n.
10 45)Split the word z into u,v and w such that |uv|<=n and |v|>=1. 46)You achieve a contradiction to pumping lemma that there exists an i Such that uviw is not in L.Then L is not a regular language. 47)

More Related Content

PART A.doc

  • 1. UNIT - II REGULAR EXPRESSIONS AND LANGUAGES ? Regular expression ? Regular Languages ? Equivalence of Finite Automata and regular expressions ? Proving languages to be not regular (Pumping Lemma) ? Closure properties of regular languages.
  • 2. LIST OF IMPORTANT QUESTIONS UNIT - II REGULAR EXPRESSIONS AND LANGUAGES PART C A 1. Show whether the language L = {0n12n | n > 0} is regular or not using pumping lemma (April/May 2017) 2. What are the closure properties of regular languages? (Nov/Dec 2016) (May/June2014), (May/June2013) 3. State the pumping lemma for Regular Languages. (May/June 2016)(Nov/Dec 2014)(Nov/Dec 2013) 4. Write Regular Expression for the set of strings over {0,1} that have atleast one.(Nov/Dec 2015) 5. What is a regular expression? (May/June2013) PART B 1) Find the regular expression of a language that consists of set of string starts with 11 as well as ends with 00 using Rij formula. (April/May2015) 2) Discuss the closure properties of regular languages. (Nov/Dec2013) (May/June2013) (Or)Prove that the class of regular sets is closed under complementation. (May/June2014) 3) Prove that A Language L is accepted by some DFA if and only if L is accepted by some NFA. (or) Let L be set accepted by a NFA and then prove that there exists a DFA that accepts L. (Nov/Dec2015) (Nov/Dec2014) (Nov/Dec2013) 4) Discuss on regular Expression. Write a regular expression for set of strings that consist of alternating 0s and 1s. (May/June 2016) (May/June2013) ii) Prove that the following languages are not regular. (May/June2013) 1) {02n | n > 1} 2) {ambnam+n | m > 1 and n > 1} (or) L = { 0m1n0m+n | m > 1 and n > 1} (Nov/Dec2013)
  • 3. UNIT - II REGULAR EXPRESSIONS AND LANGUAGES PART A 1) Show whether the language L = {0n12n | n > 0} is regular or not using pumping lemma(April/May 2017) SOLUTION: The number of states is 3n > n. w = 0n12n The length of the string |w| = 3n > n Assume xy = 0m, y = 0j , z = 0n-m . 12n xykz = xy(y)k-1z = 0m . 0j(k-1) . 0n-m . 12n xykz = 0n + j(k-1) . 12n Apply k = 0 xykz = 0n - j. 12n L Apply k = 1 xykz = 0n . 12n L Apply k = 2 xykz = 0n + j. 12n L
  • 4. Thus the Language L = {0n12n | n > 0} is not a regular Language 2) What are the closure properties of regular languages? (Nov/Dec 2016) (May/June2014), (May/June2013) CLOSURE PROPERTIES OF REGULAR LANGUAGES The regular languages are closed under i. The union of two regular languages is regular. ii. The intersection of two regular languages is regular. iii. The complement of two regular languages is regular. iv. The difference of two regular languages is regular. v. The reversal of regular languages is regular. vi. The closure of regular languages is regular. vii. The concatenation of regular languages is regular. viii.The homomorphism of regular languages is regular. ix. The inverse Homomorphism of regular languages is regular. 3) State the pumping lemma for Regular Languages (May/June 2016)(Nov/Dec 2014)(Nov/Dec 2013) PUMPING LEMMA: Let L be a regular languages. Then there exists a constant n such that for every string w in L such that |w| n. w=xyz such that i. y ii. |xy| n iii. for all i 0, xy iz L. 4) Write Regular Expression for the set of strings over {0, 1} that have atleast one. (Nov/Dec 2015) REGULAR EXPRESSION OF STRINGS {0, 1}: 1(0 + 1)* . 5) Define the term epsilon transition.[May/Jun 13] a. The is a character used to indicate null string.
  • 5. b. i.e. the string which is used simply for transition from one state to other state without any input. 6) Define the language accepted by a NFA a. We define the language of a NFA A = (Q,, ,q0,F) by b. L(A) = { w|(q0,w) F }. 7) Define the language accepted by a DFA a. We define the language of a DFA A = (Q,, ,q0,F)by b. L(A) = { w|(q0,w) is in F}. 8) Differentiate L* and L+ a. L* denotes Kleene closure and is given by L* = U Li i=0 b. example: 0* ={ ?,0,00,000, } c. Language includes empty words also. d. L+ denotes Positive closure and is given by L+= U Li i=1 9) Define Substring. A string v appears within another string w(w=uv) is called substring of w. IF w=uv, then substrings u & v are said to be prefix and suffix of w respectively 10) What is a regular expression? (May/June2013) The Language accepted by finite automata are easily described by simple expression called regular expression. A regular expression is a string that describes the whole set of strings according to certain syntax rules. These expressions are used by many text editors and utilities to search bodies of text for certain patterns etc. Let be an alphabet. The regular expression over and the sets they denote are: i. is a R.E, denotes empty set and Language L() = { }. ii. pie is a R.E denotes the set { } and Language L(pie) = { pie}. iii. A variable represented in upper case like L is any language. iv.For each a in , a is a R.E and denotes the set {a}. v. If r and s are regular expression, then i. If r and s are R.E denoting the languages R and S respectively then (r+s), ii. (rs) and (r*) are R.E that denote the sets RUS, RS and R* respectively. 11)Write a r.e to denote a language L which accepts all the strings which begin or end with either 00 or 11.
  • 6. The r.e consists of two parts: L1=(00+11) (any no of 0s and 1s) =(00+11)(0+1)* L2=(any no of 0s and 1s)(00+11) =(0+1)*(00+11) Hence r.e R=L1+L2 =[(00+11)(0+1)*] + [(0+1)* (00+11)] 12)Construct a r.e for the language over the set ={a,b} in which total number of as are divisible by 3 ( b* a b* a b* a b*)* 13)What is: (i) (0+1)* (ii)(01)* (iii)(0+1) (iv)(0+1)+ [Remember] (0+1)*= { ?, 0 , 1 , 01 , 10 ,001 ,101 ,101001, } Any combinations of 0s and 1s. (01)*={ ?, 01 ,0101 ,010101 , } All combinations with the pattern 01. (0+1)= 0 or 1,No other possibilities. (0+1)+= {0,1,01,10,1000,0101,.} 14)Reg exp denoting a language over ={1} having (i) even length of string (ii) odd length of a string. i. Even length of string R=(11)* ii. Odd length of the string R=1(11)* 15)Reg exp for: (i) All strings over {0,1} with the substring 0101 (ii) All strings beginning with 11 and ending with ab (iii) Set of all strings over {a,b}with 3 consecutive bs. (iv) Set of all strings that end with 1and has no substring 00 i. (0+1)* 0101(0+1)* ii. 11(1+a+b)* ab iii. (a+b)* bbb (a+b)* iv. (1+01)* (10+11)* 1 16)Construct a r.e for the language which accepts all strings with atleast two cs over the set ={c,b} (b+c)* c (b+c)* c (b+c)* 17)What are the applications of Regular expressions and Finite automata [Remember] a. Lexical analyzers and Text editors are two applications. Lexical analyzers: b. The tokensof the programminglanguage can be expressed using regular expressions.
  • 7. c. The lexical analyzer scans the input program and separates the tokens.For eg identifier can be expressed as a regular expression d. as: (letter)(letter+digit)* e. If anything in the source language matches with this reg exp then it is recognized as an identifier.The letter is{A,B,C,..Z,a,b,c.z} and digit is {0,1,9}.Thus reg exp identifies token in a language. f. Text editors: g. These are programs used for processing the text. For example UNIX text editors uses the reg exp for substituting the strings such as: S/bbb*/b/ h. Gives the substitute a single blank for the first string of two or more blanks in a given line. In UNIX text editors any reg exp is converted to an NFA with ?transitions, this NFA can be then simulated directly.
  • 8. 18)Reg exp for the language that accepts all strings in which a appears tripled over the set ={a} [Apply] 19)reg exp=(aaa)* 20)Reg exp for the language such that every string will have atleast one a followed by atleast one b. [Apply] 21)R=a+b+ 22)Write the exp for the language starting with and has no consecutive bs. [Apply] 23)reg exp=(a+ab)* 24)Construct a regular expression denoting odd numbers in their binary representation. [Apply] 25){0/1}*1 26)Construct a regular expression denoting even numbers in their binary representation. [Apply] 27){0/1}*0 28)Construct a regular expression denoting the set of all strings of 0 and 1 beginning with 0 and ending with 1 . [Apply] [Nov 2012] 29)0{0/1}*1 30)Construct a regular expression denoting the set of all strings over {a,b} such that all starts with a and ends with ab. [Apply] 31)a{a/b}*ab 32)Construct a regular expression denoting the set of all strings of 0 and 1 ending in 00 . [Apply] [Nov 2012] 33){0/1}*00 34)Write the regular expression for set of all strings over {0,1} that have at least one. [Apply] (Nov / Dec 2015) 35)R=(0+1)*1(0+1)* 36)Construct a regular expression denoting the set of all strings over {a,b} such that all contains three as. [Apply] 37)b*ab*ab*ab* 38)What does the following regular expression denote 0*1*2*[Analyze] 39)The set of all words over {0,1} such that all starts with 0 number of 0s or 1 0s or more number of 0s followed by similar patterns of 1s and 2s. 40)Construct a regular expression for the set of strings that consist alternate 0s and 1s. [Apply] 41)(01)* + (10)*+ 0(10)* + 1(01)*
  • 9. 42)What are the applications of pumping lemma? [Remember] Pumping lemma is used to check if a language is regular or not. (i).Assume that the language(L) is regular. 43)(ii).Select a constant n. 44)(iii).Select a string(z) in L, such that |z|>n.
  • 10. 10 45)Split the word z into u,v and w such that |uv|<=n and |v|>=1. 46)You achieve a contradiction to pumping lemma that there exists an i Such that uviw is not in L.Then L is not a regular language. 47)