Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
CSIT(CI)-503 (A)/IT-503 (A) (GS)
B.Tech., V Semester
Examination, December 2024
Grading System (GS)
Theory of Computation
Note:
-
Attempt any five questions.
किन्हीं पाँच प्रश्नों को हल कीजिए।
-
All questions carry equal marks.
सभी प्रश्नों के समान अंक हैं।
-
Missing data if any assume suitably.
लुप्त डाटा, यदि कोई हो, उचित रूप से मानें।
-
In case of any doubt or dispute the English version question should be treated as final.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
What are the components of finite automata model? किन्हीं आँटोमेटा मॉडल के घटक क्या हैं?
Construct deterministic finite automata to recognize odd number of 1's and even number of 0's. 1 की विषम संख्या और 0 की सम संख्या को पहचानने के लिए निश्चित आँटोमेटा मॉडल का निर्माण करें।
Convert the Regular expression (a+b)*abb directly into a DFA. रेगुलर एक्सप्रेशन (a+b)*abb को सीधे DFA में बदलें।
Consider the FA and construct regular expressions that are accepted by it. FA पर विचार करें और निर्मित करें रेगुलर एक्सप्रेशन जो इसके द्वारा स्वीकार किए जाते हैं।
Show id + id * id can be generated by two distinct leftmost derivations in the grammar. E → E + E / E * E / (E) / id. दिखाएँ id + id * id व्याकरण में दो अलग-अलग बाएँ व्युत्पन्न द्वारा उत्पन्न किया जा सकता है। E → E + E / E * E / (E) / id.
Can an ambiguous CFG be converted into Chomsky Normal Form. Explain briefly your answer. क्या एक अस्पष्ट CFG को चोम्स्की नॉर्मल फॉर्म में बदला जा सकता है। अपना उत्तर संक्षेप में स्पष्ट करें।
Construct PDA for the language L = {aⁿbⁿcᵐ, where n≥0, m≥0}. भाषा L = {aⁿbⁿcᵐ, जहाँ n≥0, m≥0} के लिए PDA का निर्माण करें।
Construct the PDA for the following grammar. निम्नलिखित व्याकरण के लिए PDA का निर्माण करें। X→0X3 X→0A3 A→1A2 A→12
Design a TM to accept the string L = {aⁿbⁿ}, where n(a) + n(b) = even. स्ट्रिंग L = {aⁿbⁿ}, को स्वीकार करने के लिए एक TM डिज़ाइन करें, जहाँ n(a) + n(b) = सम।
Give the tuple definition of Turing machine and explain the significance of movement of R/W head. ट्यूरिंग मशीन की टपल पर��भाषा दीजिए और R/W हेड की गति के महत्व को समझाइए।
Convert the following Mealy machine to an equivalent Moore machine by the tabular format. निम्नलिखित मीली मशीन को सारणीबद्ध प्रारूप के अनुसार समकक्ष मूर मशीन में परिवर्तित करें।
| Present State | Next State O/P (I/P = 0) | Next State O/P (I/P = 1) | ||
|---|---|---|---|---|
| Next State | O/P | Next State | O/P | |
| Q0 | Q1 | 1 | Q3 | 0 |
| Q1 | Q3 | 1 | Q1 | 1 |
| Q2 | Q1 | 1 | Q2 | 1 |
| Q3 | Q2 | 0 | Q0 | 1 |
Explain Chomsky hierarchy of grammar with suitable example. उपयुक्त उदाहरण सहित व्याकरण के चॉम्स्की पदानुक्रम की व्याख्या करें।
Convert CFG to GNF CFG को GNF में परिवर्तित करें। A → BB/I B → AA/0
Construct the context free grammar equivalent to a regular expression (01 + 1)* (00 + 1). रेगुलर एक्सप्रेशन (01 + 1)* (00 + 1) के समतुल्य कॉन्टेक्स्ट फ्री ग्रामर की रचना करें।
Write short note on: (Any three)
- 2-way Finite Automata
- Properties of Regular Grammar
- Multi Tape TM
- Arden's Theorem
संक्षेप टिप्पणी लिखें (कोई तीन)
- 2-वे फाइनाइट ऑटोमेटा
- प्रॉपर्टीज ऑफ़ रेगुलर ग्रामर
- मल्टी टेप TM
- आर्डेंस थ्योरम
*****