Scribd
Upload
19 views4 pages

Toc Assignement Unit2 KJD

The document contains assignments on theory of computation including regular expressions, grammars, automata and pumping lemma. It asks to write regular expressions, describe languages, draw DFAs, NFAs, convert between models and apply pumping lemma to check regularity.

Uploaded by

Patel Vatsal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views4 pages

Toc Assignement Unit2 KJD

The document contains assignments on theory of computation including regular expressions, grammars, automata and pumping lemma. It asks to write regular expressions, describe languages, draw DFAs, NFAs, convert between models and apply pumping lemma to check regularity.

Uploaded by

Patel Vatsal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Shri S’ad Vidya Mandal Institute of Technology, Bharuch

Department of Computer Science & Engineering

Academic Year 2022-2023 (Even Semester)

BE-III 6TH SEM CSE

THEORY OF COMPUTATION-3160704

Assignment –I – Unit 2
1 Write regular expressions for the following languages defined over Σ = {0, 1}:
a. The language of all the strings that do not end with 01.
b. The language of all the strings containing even number of 0’s and even number of 1’s.
c. The language accepting all the strings which are ending with 00.
d. The language accepting the strings which are starting with 1 and ending with 0
e. The language having which should have at least one 0 and atleast one 1
f. The language L which accepts all the strings which begin or end with either 00 or 11.
2 Write regular expressions for the following languages defined over Σ = {a,b}:

a) The language starting and ending with a and having any combinations of b’s between.
b) The language in which 3rd character from right end of string is always a.
c) The language which accepts all the strings with at least two b’s
d) The language consists of exactly two b’s
e) The language of all the strings with next-to-last symbol is a.
f) The language of all the strings containing substring bba.

3 Describe in simple English language represented by following regular expression-

r= (a + ab)*
4 Enlist types of grammars, types of languages and types of automata.
5 Draw DFA for the following languages defined over Σ = {a, b}:
a. The language of all the strings with next-to-last symbol is a.
b. The language of all the strings containing substring bba.

6 Draw FA for following languages:


a. L1= { w | 00 is not substring of w}
b. L2 = {w| w ends in 01}
7 Draw NFA-Λ for ((0+1)*10 + (00)) using Thomson construction method. Apply subset
construction method to convert into DFA.
8 Convert NFA- Λ to FA for following figure

9 Develop an FA corresponding to following regular expression 𝑟= (11+110)∗0 .Explain the properties


of Distinguishability of Strings and Equivalence classes, show minimum numbers of states necessary
for this FA. ( Use Equivalence theorm and Table filling/Myhill Nerode method both)
10 Convert the following NFA into its equivalent DFA using subset construction method.

11 Minimize following FA.


12 Define the steps to convert ε -NFA into NFA. Then convert the following ε -NFA into NFA.

13 Convert follwoin g NFA-^ to NFA.

14

15 Convert the given Moore machine into Mealy machine. Draw state transition diagram of Mealy
machine.
16

17 Define pumping lemma for regular language.


Show that the language L= {anbncn / n>=1} is non-regular using pumping lemma theory.

Subject Co-ordinator:
Dr Kruti Dangarwala

You might also like