Exam Details

Subject theory of computation
Paper
Exam / Course b.tech
Department
Organization Institute Of Aeronautical Engineering
Position
Exam Date July, 2018
City, State telangana, hyderabad


Question Paper

Hall Ticket No Question Paper Code: AIT002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
B.Tech IV Semester End Examinations Supplementary) July, 2018
Regulation: IARE R16
THEORY OF COMPUTATION
Time: 3 Hours (Common to CSE IT) Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Define the following terms and give an example for each: Language ii) Star closure of a language
iii) Non Deterministic Finite Automata
Define a Deterministic finite automata (DFA). Design a DFA for the language over consisting
of strings ending with 10.

2. Design NFA for recognizing relational operators of C Programming language.
Convert the following NFA to DFA.
Figure 1
UNIT II
3. Construct the NFA for the regular expression
Give regular expression for the following language L over f1; 0g where L consists of strings of
length multiples of 3.
4. Describe the closure properties of Regular Languages.
Write the right linear grammar for the regular expression
UNIT III
5. Give the context free grammar for the following language: {anbm
Convert the following grammar into CNF:
S aAa bBb "
A C a
B C b
C CDE "
D A B ab
Page 1 of 2
6. State and explain with an example pumping lemma theorem for context free languages.
Consider the Grammar with the following productions.
E E T T T F F E id
Write the leftmost and rightmost derivation and parse tree for the string id+id*id. Is the grammar
ambiguous?
UNIT IV
7. Compare DPDA and NPDA. Give one example for each.
Convert the following grammar to a PDA
I a b Ia Ib I0 I1
E I E E E E
8. Design a NPDA to accept a balanced strings of parentheses.
Explain the following
i. PDA accepting through empty stack
ii. PDA Accepting through final state.
UNIT V
9. Define a Turing machine and with a neat diagram, explain its working principle.
Design a Turing machine that will accept the language L over fa; bgwhereL fanbncng :jn 0.

10. List the different types of languages and show the relationship using chomsky hierarchy.
Define the following with an example:
i. Recursively enumerable languages
ii. Recursive languages
iii. Universal languages


Other Question Papers

Subjects

  • ac machines
  • advanced databases
  • aircraft materials and production
  • aircraft performance
  • aircraft propulsion
  • aircraft systems and controls
  • analog communications
  • analysis of aircraft production
  • antennas and propagation
  • applied physics
  • applied thermodynamics
  • basic electrical and electronics engineering
  • basic electrical engineering
  • building materials construction and planning
  • business economics and financial analysis
  • compiler design
  • complex analysis and probability distribution
  • computational mathematics and integral calculus
  • computer networks
  • computer organization
  • computer organization and architecture
  • computer programming
  • concrete technology
  • control systems
  • data structures
  • database management systems
  • dc machines and transformers
  • design and analysis of algorithms
  • design of machine members
  • digital and pulse circuits
  • digital communications
  • digital ic applications using vhdl
  • digital logic design
  • digital system design
  • disaster management
  • disaster management and mitigation
  • discrete mathematical structures
  • dynamics of machinery
  • electrical circuits
  • electrical measurements and instrumentation
  • electrical technology
  • electromagnetic field theory
  • electromagnetic theory and transmission lines
  • electronic circuit analysis
  • electronic devices and circuits
  • elements of mechanical engineering
  • engineering chemistry
  • engineering drawing
  • engineering geology
  • engineering mechanics
  • engineering physics
  • english
  • english for communication
  • environmental studies
  • finite element methods
  • fluid mechanics
  • fluid mechanics and hydraulics
  • fundamental of electrical and electronics engineering
  • fundamental of electrical engineering
  • gender sensitivity
  • geotechnical engineering
  • heat transfer
  • high speed aerodynamics
  • hydraulics and hydraulic machinery
  • image processing
  • industrial automation and control
  • instrumentation and control systems
  • integrated circuits applications
  • introduction to aerospace engineering
  • kinematics of machinery
  • linear algebra and calculus
  • linear algebra and ordinary differential equations
  • low speed aerodynamics
  • machine tools and metrology
  • mathematical transform techniques
  • mathematical transforms techniques
  • mechanics of fluids and hydraulic machines
  • mechanics of solids
  • mechanism and machine design
  • metallurgy and material science
  • microprocessor and interfacing
  • modern physics
  • network analysis
  • object oriented analysis and design
  • object oriented programming through java
  • operating systems
  • optimization techniques
  • power electronics
  • power generation systems
  • probability and statistics
  • probability theory and stochastic processes
  • production technology
  • programming for problem solving
  • pulse and digital circuits
  • reinforced concrete structures design and drawing
  • software engineering
  • strength of materials - i
  • strength of materials - ii
  • structural analysis
  • surveying
  • theory of computation
  • theory of structures
  • thermal engineering
  • thermo dynamics
  • thermodynamics
  • tool design
  • transmission and distribution systems
  • unconventional machining processes
  • waves and optics
  • web technologies