Share Pdf : Author Vivek Kulkarni Wordpress Com

Download and Preview : Author Vivek Kulkarni Wordpress Com

Report CopyRight/DMCA Form For : Author Vivek Kulkarni Wordpress Com

## Transcription

Theory of Computation Solutions for review questions. Q 1 Define the following and give suitable examples. i Regular set, ii Regular expression, i Regular set Refer to the section 3 5. ii Regular expression Refer to the section 3 2, Q 2 Prove that the language L a b n 0 is non regular using pumping lemma. We must not confuse the n in the language definition with the constant n of pumping lemma Hence we. rewrite the language definition as, L ambm 1 m 0, Step 1 Let us assume that the language L is a regular language Let n be the constant of pumping lemma. Step 2 Let us choose a sufficiently large string z such that z albl 1 for some large l 0 the length of z. is given by z 2l 1 n Since we assumed that L is a regular language and from the language. definition it is an infinite language we can now apply pumping lemma This means that we should be. able to write z as z uvw, Step 3 As per pumping lemma every string uviw for all i 0 is in L Further v 1 which means that. v cannot be empty and must contain one or more symbols. Let us consider the case when v contains a single symbol from a b Hence z uvw albl 1 which. means that the number of b s is one greater than number of a s in z Therefore as per pumping lemma we. would expect uv2w also to be a member of L However this cannot be the case as v contains only a. single symbol and pumping v would yield different number of a s and b s than what is expected by the. language definition Thus uv2w is not a member of L contradicting our assumption that L is regular. Let us now consider the case when v contains both the symbols i e a as well as b The sample v could be. written as ab or aabb and so on When we try to pump v multiple times such as for example. v2 abab or v2 aabbaabb and so on we find that even a s can follow b in the string which is against. Oxford University Press 2013 All rights reserved 2. Theory of Computation Solutions for review questions. the language definition ambm 1 according to which a s are followed by b s and not vice versa Thus. uv2w is not a member of L contradicting our assumption that L is regular. Hence language L ambm 1 m 0 is non regular, Q 3 Explain in brief the applications of finite automata.

Refer to the section 3 8, Q 4 Construct the NFA with transitions which accepts the language defined by. ab ba aa ab ba, Also convert this to a minimized DFA. Refer to the example 3 27 form the book, Q 5 Construct regular expressions defined over the alphabet a b which denote the following. i All strings without a double a, ii All strings in which any occurrence of the symbol b is in groups of odd numbers. iii All strings in which the total number of a s is divisible by 2. i Strings without double a means strings without two consecutive a s Hence the required RE is. ii Here b s exist in groups of odd numbers i e 1 3 5 and so on Hence the RE is. iii Here we require even number of a s The required RE is. b a b a b b, Oxford University Press 2013 All rights reserved 3.

Theory of Computation Solutions for review questions. Q 6 Check the following regular expressions for equivalence and justify. i R1 a bb b aa, ii R1 a b abab, R2 b a a b ab, i Let us write languages denoted by R1 and R2 as below. L R1 a b aa ab bb abb baa bba, L R2 a b aa ab ba bb. Given regular expressions R1 and R2 are not equal as the strings produced by them are not same For. example string ba cannot be generated using regular expression R1 which can be produced by R2. ii Let us write languages denoted by R1 and R2 as below. L R1 aba aaba baba abab ababb ababa, L R2 aa baa baaa baba baab. Given regular expressions R1 and R2 are not equal as the strings produced by them are not same For. example string aa cannot be produced by Regular Expression R1 which can be produced by R2. Q 7 Describe in English the sets denoted by the following regular expressions. i Let us write language denoted by the given RE, L R a b ab ba bb aba abb bbb baba abab. Given language consists of strings where two consecutive a s cannot occur. ii Let us write language denoted by the given RE, L R 0 1 00 11 01 10 000 111.

Given language consists of strings where any combination of 0 s and 1 s can be observed. Q 8 Construct an NFA with moves which accepts the language defined by. 0 1 10 00 11, Oxford University Press 2013 All rights reserved 4. Theory of Computation Solutions for review questions. The NFA with moves is, Q 9 Let R1and R2 be two regular expressions With the help of transition diagrams illustrate the three. operations on R1 and R2, Refer to the section 3 4 2 1. Q 10 Show that the regular expressions a bbb a and a bbba are equivalent. Let R1 a bbb a and R2 a bbba, Let us write language denoted by R1 as. L R1 a aa aaa bbb aaaa abbb bbba abbba, Let us write language denoted by R2 as.

L R2 a aa aaa bbb aaaa abbb bbba abbba, As we can see that languages denoted by regular expressions are same i e L R1 L R2 Therefore. regular expressions R1 and R2 are equivalent, Oxford University Press 2013 All rights reserved 5. Theory of Computation Solutions for review questions. Q 11 Give a regular expression for representing all strings over a b that do not include the sub. strings bba and abb, This essentially requires no consecutive b s The RE can be written as. Q 12 Consider the two regular expressions, R2 ab ba b a a b. i Find a string corresponding to R1 but not to R2, ii Find a string corresponding to R2 but not to R1.

iii Find a string corresponding to both R1 and R2, ii abbbbbbb. Q 13 Construct an NFA for the regular expression a b ab Convert the NFA to its equivalent DFA. and validate the answer with suitable examples, It is expected to construct a DFA that recognizes the regular set. Let us first build the NFA with moves and the convert the same to DFA. The TG for NFA with moves is as follows, Oxford University Press 2013 All rights reserved 6. Theory of Computation Solutions for review questions. Let us convert this NFA with moves to its equivalent DFA using a direct method. We have relabelled the states as well Let us see if we can minimize it The STF for the DFA looks like. We can see that states P and R are equivalent Hence we can replace R by P and get rid of R The reduced. Oxford University Press 2013 All rights reserved 7. Theory of Computation Solutions for review questions. The TG for the equivalent DFA is, Q 14 Define the term regular language. Refer to the section 3 5, Q 15 Write short note on pumping lemma for regular sets.

Refer to the section 3 6, Q 16 Construct an NFA Q q0 F for the following regular expression. 01 10 111 0 1, NFA can be drawn as below, Oxford University Press 2013 All rights reserved 8. Theory of Computation Solutions for review questions. Q 17 Prove that the regular expressions given below are equivalent. ii a bbb a, Let R1 a bbb a and R2 a bbba, Let us write language denoted by R1 as. L R1 a aa aaa bbb aaaa abbb bbba abbba, Let us write language denoted by R2 as. L R2 a aa aaa bbb aaaa abbb bbba abbba, As we can see that languages denoted by regular expressions are same i e L R1 L R2 Therefore.

regular expressions R1 and R2 are equivalent, Q 18 Describe the language accepted by the following finite automaton. Figure 3 38 Example DFA, Regular expression can be written as. a b a b a b, Q 19 Describe as simply as possible in English the language represented by 0 1 0. Let us write the language denoted by the regular expression. L R 0 00 10 000 110 0000 1110 010 0110, Given language consists of all the strings over 0 1 that ends with a 0. Q 20 Construct an NFA that recognizes the regular expression a b a b Convert it to a DFA and. draw the state transition table, Oxford University Press 2013 All rights reserved 9.

Theory of Computation Solutions for review questions. Refer to the answer for Q 13 above, Q 21 Construct a regular expression corresponding to the state diagram shown below using Arden s. Figure 3 39 Example FA, Refer to the example 3 41 from the book. Q 22 Is the following language regular Justify, L 0p 1p pp q p 1 q 1. We need to show that the following language is non regular using Pumping lemma. L 0p 1p pp q p 1 q 1, As we observe the length of every string from the language L 2p 2q 2 p q is even. Step 1 Let us assume that the language L is a regular language Let n be the constant of pumping lemma. Step 2 Let us choose a sufficiently large string z such that z xx where x 0p1qPp q for some large p q. 0 the length of z is given by z 2 p q n, Since we assumed that L is a regular language and from the language definition it is an infinite language.

we can now apply pumping lemma Hence we should be able to write z as z uvw. Step 3 As per pumping lemma every string uviw for all i 0 is in L Further v 1 which means that. v cannot be empty and must contain one or more symbols. Oxford University Press 2013 All rights reserved 10. Theory of Computation Solutions for review questions. Let us consider the case when v contains a single symbol from 0 1 We assume z uvw xx. 0p1qPp q0p1qPp q As per pumping lemma we would expect uv2w also to be a member of L However. this cannot be the case as v contains only a single symbol hence pumping v would cause the first x in. string xx to end with v and the second x of string xx to begin with v For example for z. 0p1qPp q0p1qPp q after pumping v 0 once we get z1 0p1qPp q 00 0p1qPp q which cannot be represented. as a concatenation of two equal sub strings Thus uv2w is not a member of L as it modifies the string of. the form xx to xvvx rather than xvxv This contradicts our assumption that L is regular. Let us now consider the case when v contains both the symbols i e 0 as well as 1 The sample v could be. written as 01 or 100 and so on When we try to pump v multiple times we obtain strings of the form. xv2v2x xv3v3x and so on which is against the language definition xx every string is represented as. concatenation of two equal sub strings Thus uviw for all i 0 is not a member of L This contradicts our. assumption that L is regular, Hence language L is non regular. Q 23 Construct the regular expression and finite automata for L L1 L2 over alphabet a b where. L1 all strings of even length, L2 all strings starting with b. Let us list down L1 and L2 for given conditions, L1 aa bb ab ba abab aaab aabb abbb baaa bbbb baba bbabab. L2 b bb ba baa bbb baab baaaa babbb, Now as L L1 L2. L bb ba baaa bbbb baab baba, Hence regular expression for L can be given as.

r b a b a b a b, Let us construct the NFA with moves as shown in the diagram below. Oxford University Press 2013 All rights reserved 11. Theory of Computation Solutions for review questions. Q 24 Which of the following are true Explain, 1 baa a b a b. 2 b a a b a b, 4 abcd a cd b, i Let L be the language denoted by the given RE then. L a b ab aa aba abab ba baa baab, As baa string belongs to language produced by given RE. Hence baa a b a b is TRUE, ii Let R1 b a then L1 b a ba bb aa bbb aaa baa bba.

Let R2 a b then L2 a b ab bb aa bbb aaa abb aab, Therefore L1 L2 a b aa bb aaa bbb. a a a aa aaa aaaa and b b b bb bbb bbbb, Hence a b a b aa bb aaa bbb. Therefore b a a b a b is TRUE, Oxford University Press 2013 All rights reserved 12. Theory of Computation Solutions for review questions. iii Let R1 a b then L1 a b ab bb aa bbb aaa and, Let R2 b c then L2 b c bc bb cc bbb ccc then. Therefore L1 L2 b bb bbb, Hence a b b c is FALSE, iv Let L be the language denoted by the given RE a cd b then.

L ab abab acdb acdcdb acdbacdb abacdb, abcd does not belong to language L. Therefore abcd a cd b is FALSE, Q 25 Construct the regular expressions for the following DFAs. Figure 3 40 Example DFAs, i The state equations for the given DFA are. B A11 using Arden s Theorem, Substituting for B in A. A A0 A11 0, 0 11 0 using Arden s Theorem, Hence A 0 11 0.

A being the final state regular expression for the given DFA is 0 11 0. Oxford University Press 2013 All rights reserved 13. Theory of Computation Solutions for review questions. ii Let the third state label be C, The state equations for the given DFA are. C A1 B1 C1, Let us try to simplify the equations, A00 using Arden s Theorem. Substituting B in C we get, C A1 A00 1 C1, A 1 00 1 C1. A 1 00 1 1 using Arden s Theorem, Substituting C in A we get. A 1 00 1 1 0, 1 00 1 1 0, Therefore B 1 00 1 1 0 00.

Both A and B are the final states for the DFA Hence the regular expression pertaining to the DFA is. 1 00 1 1 0 00, Q 26 Which of the following languages are regular sets Justify your answer. ii 0m 1n 0m n m 1 and n 1, i It is given that n 1, For n 1 02n 02 length 2. Oxford University Press 2013 All rights reserved 14. Theory of Computation Solutions for review questions. For n 2 02n 04 length 4, For n 3 02n 06 length 6, Hence length of each string is multiples of 2 which is even length. The language 02n n 1 is a regular language that can be denoted by the regular expression 00. ii 0m 1n 0m n m 1 and n 1 is not a regular set Refer to the answer for the question 3 22 above. Q 27 Find out whether given languages are regular or not. 1 L ww w 0 1, 2 L 1k k n2 n 1, Both the given language are not regular. 1 Refer to the example 3 45 from the book, 2 Refer to the example 3 43 from the book.

Q 28 With the help of a suitable example prove regular sets are closed under union . Theory of Computation Solutions for review questions Oxford University Press 2013 All rights reserved 1 Author Vivek Kulkarni vivek kulkarni yahoo com