Download PTU B.Tech 2020 March CSE-IT 7th and 8th Sem BTCS 702 Theory Of Computation Question Paper

FirstRanker.com

Roll No. [ ] [ ] [ ] [ ] Total No. of Pages : 02
Total No. of Questions : 18

--- Content provided by​ FirstRanker.com ---

--- Content provided by‌ FirstRanker.com ---

INSTRUCTION TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt ANY FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students have to attempt ANY TWO questions.

SECTION-A

--- Content provided by‍ FirstRanker.com ---

1. Define Mealy and Moore machines.
2. Define the term acceptability of a string.
3. Define pumping lemma for regular sets.
4. Differentiate between left linear and right linear regular grammar.

--- Content provided by FirstRanker.com ---

5. Define yield and ambiguity in CFG.
6. Give example CNF and GNF productions.
7. Differentiate between deterministic and non-deterministic PDA.
8. Give rules for converting CFG to PDA.
9. Give instantaneous description of Turing machine.

--- Content provided by‌ FirstRanker.com ---

10. What do you mean by halting problem of TM?

SECTION-B

1. Construct a DFA equivalent to :
   M= ({q0, q1, q2, q3},{0,1}, d, q0, {q3}), where d is given by following state table :
   

   State/Z	a	b
   q0	q0	q1
   q1	q2	q1
   q2	q3	q3

--- Content provided by‌ FirstRanker.com ---

2. Explain in detail the Chomsky classification of languages.
3. Define regular sets and write its closure properties.
4. Prove that P + PQ*Q = a*bQ* where P = b + aa*b and Q is any regular expression
5. Describe any two representation of TM.
6. Find a reduced grammar equivalent to the given grammar.
   

   --- Content provided by‍ FirstRanker.com ---

   S—> AC|B, A—>a, C—>c|BC, E—>aA|e

SECTION-C

1. Find a grammar in GNF equivalent to the grammar
   E->E+T|T
   T-> T*F|F
   

   --- Content provided by⁠ FirstRanker.com ---

   F->(E)|a
2. Design Turing Machine of {0ⁿ1ⁿ | n> 1}.
3. Describe PDA with its representations. Also write rules of converting PDA to CFG.

NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any page of Answer Sheet will lead to UMC against the Student.

FirstRanker.com

--- Content provided by​ FirstRanker.com ---