Questions for work out

Reg No:____________ Name:___________________




HEERA COLLEGE OF ENGINEERING AND TECHNOLOGY

.FIFTH SEMESTER, B.TECH DEGREE, FIRST SERIES EXAMINATION OCTOBER 2023
CSE
CST 301
FORMAL LANGUAGES AND AUTOMATA THEORY
Duration: 2 Hours Max. Marks: 50
Course Outcome: At the end of the semester students will be able to learn
Classify a given formal language into Regular, Context-Free, Context Sensitive, Recursive
CO1
or Recursively Enumerable. [Cognitive knowledge level: Understand]
Explain a formal representation of a given regular language as a finite state automaton,
CO2 regular grammar, regular expression and Myhill-Nerode relation. [Cognitive knowledge
level: Understand]
Design a Pushdown Automaton and a Context-Free Grammar for a given context-free
CO3
language. [Cognitive knowledge level : Apply]
Design Turing machines as language acceptors or transducers. [Cognitive knowledge level:
CO4
Apply]
CO5 Explain the notion of decidability. [Cognitive knowledge level: Understand]


PART – A
(Answer all questions. Each carries 3 marks)

1. Design DFA for the language L={anbm/ n,m≥1 :{a,b}}.
(CO No: 2)
2. Write the regular grammer over the alphabet(a.b) having the language which contains
exactly one 'a' (CO No: 2)
3. Write the regular expression on the language over (0,1) which contains atleast one pair
consecutive o’s. (CO No: 2)
4. Prove that the language L= { 0n1n | n ∈ N} is not regular.
(CO No: 2)
5. Compare NFA and DFA. (CO No: 1)


PART – B

(Answer any one full question from each module)