Scribd
Upload
15 views2 pages

Worksheet 5

Uploaded by

Parimala G
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
15 views2 pages

Worksheet 5

Uploaded by

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

UNIT-1

Worksheet-5
Problems related to Equivalence of Finite Automata and Regular Languages and Regular
Grammars
PART A
1. Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba
b) ab(ab)*bba
c) ab(a+b)*bba
d) All of the mentioned
2. Under which of the following operations, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
3. Ragu is asked to make an automaton which accepts a given string for all the occurrences of ‘1001’ in it. How many number
of transitions would John use such that the string processing application works?
a) 9
b) 11
c) 12
d) 15

4. Which of the following does not represent the given language? Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}

5. Which among the following looks similar to the given expression?


((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}

6. RR* can be expressed in which of the forms:


a) R+
b) R-
c) R+ U R-
d) R

7. Which of the following represents a language which has no pair of consecutive 1’s if = {0,1}?
a) (0+10)*(1+ε)
b) (0+10)*(1+ε)*
c) (0+101)*(0+ε)
d) (1+010)*(1+ε)

8. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular
expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2

9. Let N (Q, , , q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, , ’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}
c) Q’ = {q0}
d) All of the mentioned

10. If L1 and L2 are regular languages, L1 (L2 U L1)’ will be


a) regular
b) non regular
c) may be regular
d) none of the mentioned

PART-B

1. Describe a Regular Expression. Write a Regular Expression for the set of strings that consists of alternating 0’s and
1’s.
2. Examine whether the language L=(0 n 1 n | n>=1) is regular or not? Justify your answer.
3. Construct Finite Automata equivalent to the regular expression (ab+a)*
4. Construct NDFA for given RE using Thomson rule.
i) a(a+b)* ab
ii) (a.b)*
iii) (a+b)
5. Find the Regular Expression equivalent for the given Finite Automata.

6. Evaluate the equalities for the following RE and prove for the same

(i) b+ab* +aa*b+aa*ab*

(ii) a*(b+ab*).

(iii) a(a+b)*+aa(a+b)*+aaa(a+b)*

7. Find the Regular Expression equivalent for the given Finite Automata.

8. Construct a DFA which is equivalent to the following regular expression:


00 ∪ (1 ∪ 01)(11 ∪ 0)∗10 ∗

You might also like