Theory Of Computation

Course: B.Tech Code: 601 Branch: AL Date: May 2024

Save as PDF

Opens your browser print dialog — select "Save as PDF" to download.

Total No. of Questions: 8
[Total No. of Printed Pages : 4
[2]
Roll No .......................................

AL-601 (GS)

B.Tech. VI Semester

Examination, May 2024

Grading System (GS)

Theory of Computation

Time : Three Hours

Maximum Marks : 70

Note: i) Attempt any five questions.

किन्हीं पाँच प्रश्नों को हल कीजिए।

ii) All questions carry equal marks.

सभी प्रश्नों के समान अंक हैं।

iii) In case of any doubt or dispute the English version

question should be treated as final.

किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा

के प्रश्न को अंतिम माना जायेगा।

1.
a) Say whether the NFA accepts the following or not

NFA निम्नलिखित को स्वीकार करता है या नहीं बताइए।

  1. abaa
  2. abab
Diagram for Question
b) Construct a NFA second last symbol is zero over the alphabet {0, 1} than convert in DFA.

NFA का निर्माण करें जिसका दूसरा अंतिम प्रतीक DFA में कन्वर्ट

की तुलना में वर्णमाला {0, 1} पर शून्य है।

2.
a) Explain 'Finite State Machines with Outputs'. Discriminate between Mealy and Moore machines.

'Finite State Machines with Outputs' की व्याख्या करें। मीली

और मूर मशीनों के बीच भेदभाव करें।

b) Design a DFA which accept the string starting symbol differ from ending symbol over the alphabet {0, 1}. Show dead state if any.

ए��� DFA डिज़ाइन करें जो स्ट्रिंग के शुरुआती प्रतीक को वर्णमाला

{0, 1} पर समाप्त होने वाले प्रतीक से भिन्न स्वीकार करता है। यदि

कोई हो तो Dead state दिखाएँ।

3.
Minimize the following automata

निम्नलिखित ऑटोमेटा को छोटा करें

Diagram for Question
State Inputs
0 1
→q0 q1 q2
q1 q3 q4
q2 q4 q3
q3 q5 q5
q4 q5 q5
*q5 q5 q5
4.
a) Construct context free grammar for L = {wcwR | w in (a+b)*}, Reverse of w is denoted as wR.

L = {wcwR | के लिए संदर्भ मुक्त व्याकरण का निर्माण करें w in

(a+b)*}, w का उल्टा wR के रूप में दर्शाया गया है।

AL-601 (GS) PTO
b) Define a non-deterministic PDA. How a DPDA differs from a non-deterministic PDA?

नियतात्मक PDA को परिभाषित कीजिए। कैसे एक DPDA एक गैर

नियतात्मक PDA से अलग है?

5.
a) Find the Greibach normal form grammar equivalent to the following:

निम्नलिखित के बराबर ग्रेबैच सामान्य रूप व्याकरण खोजें

CFG: S → AB | BS | 1B → SA | 0

b) What do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?

पार्सिंग से आपका क्या मतलब है? एक व्याकरण में अस्पष्टता का पता

लगाने के लिए लेफ्ट मोस्ट और राइट मोस्ट व्युत्पत्ति कैसे मदद करती

है?

6.
Construct a PDA accepting by empty stack each of the following language.

निम्नलिखित में से प्रत्येक भाषा को खाली स्टैक द्वारा स्वीकार करते हुए

एक PDA का निर्माण करे��।

  1. an bn cm where n, m ≥ 1
  2. an b2n n ≥ 0
7.
a) Design a Turing Machine which computes the multiplication of two numbers.

एक ट्यूरिंग मशीन डिज़ाइन करें जो दो संख्याओं के गुणन की गणना

करती है।

[4]
b) State pumping lemma for regular languages. Prove that the language {an | n is prime number.} is not regular. Where n is prime number.

नियगित भाषाओं के लिए पंपिंग लेम्मा स्टेट करें। सिद्ध करें कि भाषा

{an | n अभाज्य संख्या है।} नियगित नहीं है। जहाँ n अभाज्य संख्या है।

8.
Write short note on (any three):

संक्षिप्त टिप्पणियाँ लिखें (कोई तीन)

  1. Halting problem
  2. Decidability
  3. Mealy Machine
  4. CNF
AL-601 (GS) Contd...