際際滷

際際滷Share a Scribd company logo

unit 2 part b.docx

Download as DOCX, PDF
karthikeyan Muthusamy
karthikeyan Muthusamy

The document discusses several topics related to regular languages and regular expressions: 1. It proves that the language L={0n2/n is an integer, n>1} is not regular by showing that the length of strings in L exceeds the number of states in any finite automaton recognizing L. 2. It defines regular expressions and describes their syntax and how they are used to represent regular languages. 3. It provides a regular expression (01)*+(10)*+0(10)*+1(01)* for the language of strings with alternating 0s and 1s. 4. It proves several example languages such as {02n|n>1} are not regular by using

1 of 6
10 PART B 1. Show that L = {0n2 / n is an integer, n > 1} is not regular. (or) Show that the set L = {0i2 |i > 1} not regular.(Nov/Dec2015) (Nov/Dec2014) (May/June2014) SOLUTION: Let i = n2 and L = { 0i / i > 1}. The number of states is i > n. Take string w = 0i The length of the string |w| = i > n. Assume xy = 0m, y = 0j , z = 0i-m xykz = xy(y)k-1z = 0m. 0j(k-1). 0i-m = 0i. 0j(k-1) Apply i = n2 xykz = 0n2 + j(k-1) Apply k = 0 xykz = 0n2 j L Apply k = 0 xykz = 0n2 + j L Thus the Language L is not a regular Language. 2. Discuss on regular Expression.(May/June 2016) (May/June2013) REGULAR EXPRESSION: 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. i. For each a in 裡 , a is a R.E and denotes the set {a}.
11 ii. 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.. 3. Write a regular expression for set of strings that consist of alternating 0s and 1s. (May/June 2016) Consider the regular expression for the language consisting of a single string 01. The star operator is used to get an expression of all strings of the form 010101 The basic rules for RE tells us that 0 and 1 are expressions denoting the languages {0} and {1}, respectively. If we concatenate the two expressions, we get a regular expression for the language {01}; RE = 01 Now, to get all strings consisting of zero or more occurrences of 01, Regular expression (01)* and get L(01)*. Since it only includes strings beginning with 0. To account for strings that starts with 1 and strings that end with 0 or with 1: (01)* + (10)*+ 0 (10)*+ 1(01)* 4. Prove that the following languages are not regular (May/June2013) (Nov/Dec2013) 1. {02n | n > 1} SOLUTION: Let L be a regular language. The number of states are 2n > n. Let w = 0i, i > 1 where, i = 2n. w = xyz |w| = 2n > n. Assume xy = 0m, y = 0j, z = 0i-m xykz = xy(y)k-1z
12 = 0m. 0j(k-1). 0i-m = 0i + j(k-1) Apply i = 2n xykz = 02n + j(k-1) Apply k = 0 xykz = 02n - j L Apply k = 1 xykz = 02n L Apply k = 2 xykz = 02n + j L Thus Language L = {02n | n > 1} is not a regular. 5. {ambnam+n | m > 1 and n > 1} (or) L = { 0m1n0m+n | m > 1 and n > 1} SOLUTION: Let L be a regular language. The number of states are 2m+2n > n. . w = ambnam+n |w| = 2m+2n > n. Assume xy = am, y = aj, z = an-m. bn1. am+n1 xykz = xy(y)k-1z = am . aj(k-1) . an-m. bn1. am+n1 xykz = an + j(k-1) . bn1. am+n1 Apply k = 0 xykz = an - j . bn1. am+n1 L Apply k = 1 xykz = an. bn1. am+n1 L Apply k = 2 xykz = an + j . bn1. am+n1 L Thus Language L = {ambnam+n |m>=1 and n>=1} is not a regular.
13 6. Construction of - NFA from a regular expression Basis: Automata for , and a are (a),(b) and (c) respectively. a) Accepting b) Accepting c) Accepting a Induction: Automata for P+Q, PQ and P* are (d), (e) and (f) respectively. d) P+Q e) PQ f) P* Example: Construct -NFA for the regular expression (a|b)*|c Solution: using Thompson's Construction. First we construct the union of a and b: Next we construct the Kleene Star of the previous union:
Finally we create the union between this and the next symbol c: 7. Construction of regular expression from Finite Automata: Ardens theorem: Let P and Q be two regular expression over . If P does not contain then the equation in R=Q+RP has unique solution (i.e only one solution) given by R=QP* Method for finding regular expression of Finite automata in transition diagram representation using Ardens theorem: The following assumptions are made regarding the finite automata. i. The finite automaton does not have - moves. ii. It has only one initial state, say q0. iii. Its states are q0,q1.....qn i) Qi is the regular expression representing the set of string accepted by the automata even through qi is a final state. ii) ij denotes the regular expression representation the set of labels of edges from vi to vj when there is no such edge ij= .Consequently, we can get the following set of equation in Q1, .Qn Q1= Q1 11+ Q2 21+.+ Qn n1+ Q2= Q1 12+ Q2 22+.+ Qn n2 .. .
.. Qn= Q1 1n+ Q2 2n+..+ Qn nn By repeatedly applying substitutions and Ardens theorem we can express Ri in terms of ijs for getting the set of strings recognized by the automata, we have to take union of all RisCorresponding to final states. Example1: Derive a regular expression from the following given FA? Sol: q1= +q10................(1) q2=q11+q21...............(2) q3=q20+q30+q31 ..........(3) (2) q2=q11+q21 q2=q1 11* ...........(4) (1) q1= +q10 (Apply Ardens theorem) q1=0* q1=0* (4) q2=0*11* q2=0*1*

More Related Content

unit 2 part b.docx

  • 1. 10 PART B 1. Show that L = {0n2 / n is an integer, n > 1} is not regular. (or) Show that the set L = {0i2 |i > 1} not regular.(Nov/Dec2015) (Nov/Dec2014) (May/June2014) SOLUTION: Let i = n2 and L = { 0i / i > 1}. The number of states is i > n. Take string w = 0i The length of the string |w| = i > n. Assume xy = 0m, y = 0j , z = 0i-m xykz = xy(y)k-1z = 0m. 0j(k-1). 0i-m = 0i. 0j(k-1) Apply i = n2 xykz = 0n2 + j(k-1) Apply k = 0 xykz = 0n2 j L Apply k = 0 xykz = 0n2 + j L Thus the Language L is not a regular Language. 2. Discuss on regular Expression.(May/June 2016) (May/June2013) REGULAR EXPRESSION: 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. i. For each a in 裡 , a is a R.E and denotes the set {a}.
  • 2. 11 ii. 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.. 3. Write a regular expression for set of strings that consist of alternating 0s and 1s. (May/June 2016) Consider the regular expression for the language consisting of a single string 01. The star operator is used to get an expression of all strings of the form 010101 The basic rules for RE tells us that 0 and 1 are expressions denoting the languages {0} and {1}, respectively. If we concatenate the two expressions, we get a regular expression for the language {01}; RE = 01 Now, to get all strings consisting of zero or more occurrences of 01, Regular expression (01)* and get L(01)*. Since it only includes strings beginning with 0. To account for strings that starts with 1 and strings that end with 0 or with 1: (01)* + (10)*+ 0 (10)*+ 1(01)* 4. Prove that the following languages are not regular (May/June2013) (Nov/Dec2013) 1. {02n | n > 1} SOLUTION: Let L be a regular language. The number of states are 2n > n. Let w = 0i, i > 1 where, i = 2n. w = xyz |w| = 2n > n. Assume xy = 0m, y = 0j, z = 0i-m xykz = xy(y)k-1z
  • 3. 12 = 0m. 0j(k-1). 0i-m = 0i + j(k-1) Apply i = 2n xykz = 02n + j(k-1) Apply k = 0 xykz = 02n - j L Apply k = 1 xykz = 02n L Apply k = 2 xykz = 02n + j L Thus Language L = {02n | n > 1} is not a regular. 5. {ambnam+n | m > 1 and n > 1} (or) L = { 0m1n0m+n | m > 1 and n > 1} SOLUTION: Let L be a regular language. The number of states are 2m+2n > n. . w = ambnam+n |w| = 2m+2n > n. Assume xy = am, y = aj, z = an-m. bn1. am+n1 xykz = xy(y)k-1z = am . aj(k-1) . an-m. bn1. am+n1 xykz = an + j(k-1) . bn1. am+n1 Apply k = 0 xykz = an - j . bn1. am+n1 L Apply k = 1 xykz = an. bn1. am+n1 L Apply k = 2 xykz = an + j . bn1. am+n1 L Thus Language L = {ambnam+n |m>=1 and n>=1} is not a regular.
  • 4. 13 6. Construction of - NFA from a regular expression Basis: Automata for , and a are (a),(b) and (c) respectively. a) Accepting b) Accepting c) Accepting a Induction: Automata for P+Q, PQ and P* are (d), (e) and (f) respectively. d) P+Q e) PQ f) P* Example: Construct -NFA for the regular expression (a|b)*|c Solution: using Thompson's Construction. First we construct the union of a and b: Next we construct the Kleene Star of the previous union:
  • 5. Finally we create the union between this and the next symbol c: 7. Construction of regular expression from Finite Automata: Ardens theorem: Let P and Q be two regular expression over . If P does not contain then the equation in R=Q+RP has unique solution (i.e only one solution) given by R=QP* Method for finding regular expression of Finite automata in transition diagram representation using Ardens theorem: The following assumptions are made regarding the finite automata. i. The finite automaton does not have - moves. ii. It has only one initial state, say q0. iii. Its states are q0,q1.....qn i) Qi is the regular expression representing the set of string accepted by the automata even through qi is a final state. ii) ij denotes the regular expression representation the set of labels of edges from vi to vj when there is no such edge ij= .Consequently, we can get the following set of equation in Q1, .Qn Q1= Q1 11+ Q2 21+.+ Qn n1+ Q2= Q1 12+ Q2 22+.+ Qn n2 .. .
  • 6. .. Qn= Q1 1n+ Q2 2n+..+ Qn nn By repeatedly applying substitutions and Ardens theorem we can express Ri in terms of ijs for getting the set of strings recognized by the automata, we have to take union of all RisCorresponding to final states. Example1: Derive a regular expression from the following given FA? Sol: q1= +q10................(1) q2=q11+q21...............(2) q3=q20+q30+q31 ..........(3) (2) q2=q11+q21 q2=q1 11* ...........(4) (1) q1= +q10 (Apply Ardens theorem) q1=0* q1=0* (4) q2=0*11* q2=0*1*