# Author Vivek Kulkarni Wordpress Com-Books Pdf

01 Dec 2019 | 356 views | 132 downloads | 20 Pages | 506.43 KB

Share Pdf : 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

## Related Books

###### Interictal to ictal transition in human TLE insights from

Wendling et al Interictal to ictal transition in TLE J Clin Neurophysiol 2005 Oct 22 5 343 56 Interictal to ictal transition in human TLE insights from a computational model of intracerebral EEG Abbreviated title Model based study of interictal to ictal transition in TLE F WENDLING A HERNANDEZ J J BELLANGER P CHAUVEL F BARTOLOMEI INSERM U642 Rennes F 35000 France

###### Libro I LA MAGIA NATURAL Cap tulo 1

Cap tulo 1 PLAN DE TODA LA OBRA Debido a que hay tres clases de mundos a saber el Elemental el Celeste y el Intelectual y cada inferior es gobernado por su superior y recibe sus influencias de modo que el Arquetipo mismo y el Creador sobe rano nos comunica las virtudes de su omnipotencia a trav s de los Angeles los Cielos las Estrellas los Elementos los Animales las Plantas los

###### Los l mites del deber de obediencia del trabajador en la

objeto de esta tesis ha sido el an lisis de esas posibilidades de resistencia pero solo y exclusivamente en el mbito del contrato de trabajo Las relaciones de trabajo presentan muchas particularidades por la concurrencia de

###### M STICA CIUDAD DE DIOS Parte 3 CAPITULO 19

1 M STICA CIUDAD DE DIOS Parte 3 CAPITULO 19 Contiene la ltima parte del cap tulo 21 del Apocalipsis en la concepci n de Mar a Sant sima 283 El texto de la ltima y tercera parte del Apocalipsis cap tulo 21 que voy explicando es como se sigue Y los fundamentos del muro de la ciudad estaban adornados

###### PROCEDIMIENTO DE OPOSICI N

DIRE C T R I C E S D E M A R C A S INSTI TU TO NACIONAL D E PROPI EDAD INDUS TRI AL I NAPI CHIL E 3 I Generalidades A Naturaleza de la oposici n 1 La oposici n a la solicitud de registro de una marca comercial es una acci n mediante la cual un tercero interesado pide que una solicitud de registro no se convierta en marca registrada por considerar que incurre en alguna de las

###### MARBY DAYANA GIRALDO GARC A

1 estudio del direccionamiento y los protocolos de enrutamiento basados en ipv6 marby dayana giraldo garc a universidad de san buenaventura cali

###### Isabel Louren o 100 75 Fundamentos 95 75 de Contabilidade

Fundamentos de Contabilidade Financeira Isabel Costa Louren o Ana Isabel Morais Ana Isabel Lopes Coordena o Teoria e Casos Aprenda contabilidade com base em casos de empresas portuguesas de sucesso EDI ES S LABO Isabel Louren o Ana Isabel Morais Ana Isabel Lopes Pedro Ferreira Cl udio Pais Il dio Lopes Nuno Magro S lvia Casa Nova Professora Associada com Agrega o do ISCTE IUL

FUNDAMENTOS Y DESARROLLOS PSICOANAL TICOS CURSOS DE DOCTORADO PERIODO DE INVESTIGACI N II MATERIA TEXTOS FUNDAMENTALES PARA EL PSICOAN LISIS HUMOR Y PSICOAN LISIS UNA LECTURA DE LOS TEXTOS DE FREUD Federico Garc a Serrano Facultad de Psicolog a Universidad Complutense Madrid Septiembre de 2006 Humor y Psicoan lisis P gina 1 de 196 1 INTRODUCCI N 1 1 HUMOR Y

###### RODGERS WILSON WONG WONG FUNDAMENTOS DE ENFER

A 10 edi o de Wong Fundamentos de Enfermagem Pedi trica apresenta inova es e atualiza es de conte do as etapas do ciclo de vida da inf ncia e adolesc ncia o cuidado centrado na fam lia e na comunidade e a pr tica baseada em evid ncias como marco de refer ncia para a composi o de cada um dos cap tulos do livro Na atual edi o traduzida para o portugu s o conte do

###### Cap tulo 1

Dire tor de Comunica o n o um cargo um pa pel que Kevin desempenhar quando comunicar as a es da equipa ao resto da organiza o A Teoria Alargada do Trabalho n o v o trabalho em termos de estrutura organizacional mas em termos de modelos de neg cio Os organigra mas descrevem as rela es hier rquicas no seio de uma empresa mas pouco nos dizem sobre o

###### ST PEPPER User s Guide Third Edition

HHA PEPPER User s Guide Second Edition 5 Medicare home health care consists of skilled nursing physical therapy occupational therapy speech therapy aide services and medical social work provided to beneficiaries in their homes CMS uses a prospective payment system PPS that establishes a predetermined reimbursement rate for each 60 day