Wednesday, April 21, 2010

TOC Question Paper Unit - II C

MCA SEM II
Subject Code: 620007
     Subject Name: Theory of Computation
UNIT – II
Question List -C

Q.1
(a)
Do as Directed.



(i)                 Define Regular Languages and Regular Expression over Σ
2


(ii)              Give the Regular Expression for The Language of C identifiers.
1


(iii)            List out any three Application of Regular Expression.
1


(iv)             What is the Precedence order for Regular Expression?
1

(b)
Draw the FA for all strings over {0, 1} that begin and end with 111.
5
Q.2
(a)
Define Distinguishable String With Respect to Language.
Draw the FA for Regular Expression (a + b)* abb.
5

(b)
Explain Different Types of State in Finite Automata.
Draw DFA that will recognize the set {1, 00} and categorized all state in DFA according to its type.
5


OR


(b)
Prove the Following.
(i)       (111*)* = (11 + 111)*
(ii)              (00*1)*1 = 1 + 0(0+10)*11
5
 

TOC Question Paper Unit - II B

MCA SEM II
Subject Code: 620007
     Subject Name: Theory of Computation
UNIT – II
Question List -B

Q.1
(a)
Do as Directed.



(i)                 Given the two Regular Expressions.
r = 0* + 1*
s = 01* + 10* + 1*0 + (0*1)*
             (1) Find the string corresponding to r and s.
             (2) Find the string corresponding neither to r nor to s.
2


(ii)              Explain the Language for given.
(1) 0*1 (0*10*1)* 0*.
              (2) (1+01)* (Λ+0+00) (1+10)*
2


(iii)            Find the String that is not in Language Represented by Regular Expression a*(ab)*b* and string should be shortest.
1

(b)
Define Finite State Machine.
List out Characteristics & Applications of FSM. Explain with Example of Automatic Door.
5
Q.2
(a)
Define Extended Transition Function δ*.
Draw the DFA for All string over {0, 1} that contains substring 110 and 001.
5

(b)
In which case Initial State become the Accepting State in DFA.
Draw DFA for L={x є Σ* |x contains the substring 010, but does not contain the substring 0101}
5


OR


(b)
Define Transition Diagram and Transition Table.
Draw DFA for all string over {0, 1} that contains at least two 0’s and at most one 1.
5
 

TOC Question Paper Unit - II A

MCA SEM II
Subject Code: 620007
     Subject Name: Theory of Computation
UNIT – II
Question List -A

Q.1
(a)
Do as Directed.



(i)                 Given the two Regular Expressions.
r = 0* + 1*
s = 01* + 10* + 1*0 + (0*1)*
              (1) Find the string corresponding to r but not to s.
              (2) Find the string corresponding to s but not to r.
2


(ii)              Find the Regular Expression for given.
(1)   All String that do not end with 01.
(2)   All String that contain no more than one occurrence of the string 00.
(3)   All String that contains exactly two 0’s.
3

(b)
Prove the Following.
(i)                 0+1(1+Л)*0 = 1*0
(ii)              (aa*bb*) = Л + a (a+b)*b
5
Q.2
(a)
Define Finite Automata.
Draw FA for all string over {0,1} that contain 1001 or 0110
5

(b)
Define Acceptance by Finite Automata.
Draw the FA for Regular Expression (1+01)* (Л+0+00) (1+10)* and Check Whether the FA Accept the Following Strings or Not
(i)                 100011100     
(ii)       1110111001101
5


OR


(b)
Define Transition Function.
Draw FA for M=({q0,q1,q2,q3},{0,1},q0,{q3},δ) where δ is defined as
δ
0
1
q0
q1
q0
q1
q2
q0
q2
q3
q0
q3
q3
q3
Give the Regular Expression for a Language Which is accepted by FA.
5
 

Tuesday, April 20, 2010

Assignment – 8 Regular Language & Finite Automata

B. H. Gardi College of Engineering and Technology,Rajkot
Department of MCA
MCA Semester – II
Subject: 620007 – Theory of Computation

Assignment – 8
Regular Language & Finite Automata

Date: 17-Apr-2010


1
Regular Language
2
Regular Expression
3
Regular Language & Regular Expression Over Σ
4
Finite Automata / Finite State Machine / DFA
5
Transition Table
6
Types of State
7
Transition Diagram
8
Transition Function ( δ )
9
Extended Transition Function ( δ* )
10
String Accepted by FA
11
String Rejected by FA
12
Regular Language ( In Context of  FA)
13
Distinguishable String With Respect To Language



Note: Write all Answers with Example.