This download link is referred from the post: PTU B.Tech Question Papers 2020 March (All Branches)
Roll No. [ ] [ ] [ ] [ ] Total No. of Pages : 02
Total No. of Questions : 18
--- Content provided by FirstRanker.com ---
B.Tech.(CSE) (2012 to 2017) (Sem.-7,8)THEORY OF COMPUTATION
Subject Code : BTCS-702
M.Code : 71894
Time : 3 Hrs. Max. Marks : 60
--- Content provided by FirstRanker.com ---
INSTRUCTION TO CANDIDATES :
- SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
- SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt ANY FOUR questions.
- SECTION-C contains THREE questions carrying TEN marks each and students have to attempt ANY TWO questions.
SECTION-A
--- Content provided by FirstRanker.com ---
Answer Briefly :- Define Mealy and Moore machines.
- Define the term acceptability of a string.
- Define pumping lemma for regular sets.
- Differentiate between left linear and right linear regular grammar.
- Define yield and ambiguity in CFG.
- Give example CNF and GNF productions.
- Differentiate between deterministic and non-deterministic PDA.
- Give rules for converting CFG to PDA.
- Give instantaneous description of Turing machine.
- What do you mean by halting problem of TM?
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
- Construct a DFA equivalent to :
M= ({q0, q1, q2, q3},{0,1}, Ī“, q0, {q3}), where Ī“ is given by following state table :
State/Z a b q0 q0 q1 q1 q2 q1 q2 q3 q3 - Explain in detail the Chomsky classification of languages.
- Define regular sets and write its closure properties.
- Prove that P + PQ*Q = a*bQ* where P = b + aa*b and Q is any regular expression
- Describe any two representation of TM.
- 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
--- Content provided by FirstRanker.com ---
SECTION-C
- 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 - Design Turing Machine of {0n1n | n> 1}.
- 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.
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU B.Tech Question Papers 2020 March (All Branches)
--- Content provided by FirstRanker.com ---