Scribd
Upload
177 views1 page

Automata Theory Exam Guide

This document contains instructions and questions for an exam on formal languages and automata theory. [Section A] contains short answer questions about the differences between acceptance in a PDA with null stack vs final state, the definition of a context-sensitive grammar, and comparing the computational powers of PDAs and Turing machines. [Section B] requires longer explanations of nondeterministic PDAs, closure properties of context-free grammars, and the pumping lemma with an example. [Section C] involves designing a PDA to recognize even length palindromes and explaining Turing machines and ways to represent them. The objectives cover writing formal notations, designing automata, grammars, equivalence of languages, and computability.

Uploaded by

JANMEET
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
177 views1 page

Automata Theory Exam Guide

This document contains instructions and questions for an exam on formal languages and automata theory. [Section A] contains short answer questions about the differences between acceptance in a PDA with null stack vs final state, the definition of a context-sensitive grammar, and comparing the computational powers of PDAs and Turing machines. [Section B] requires longer explanations of nondeterministic PDAs, closure properties of context-free grammars, and the pumping lemma with an example. [Section C] involves designing a PDA to recognize even length palindromes and explaining Turing machines and ways to represent them. The objectives cover writing formal notations, designing automata, grammars, equivalence of languages, and computability.

Uploaded by

JANMEET
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Roll

Date
No.

CGC COLLEGE OF ENGINEERING


B.TECH (CSESem.–5th)
2nd Sessional
Subject: Formal Language & Automata Theory
Subject Code: (BTCS-502-18)
Time: 1.0 Hr. Max. Marks: 24
INSTRUCTIONS TO CANDIDATES:
1. SECTION-A is COMPULSORY.
2. ATTEMPT ANY TWO QUESTIONS FROM SECTION - B AND ONE QUESTION FROM SECTION – C.
Course Objectives
CO1: Write a formal notation for strings, languages and machines.
CO2: Design finite automata to accept a set of strings of a language.
CO3: Design context free grammars to generate strings of context free language.
CO4: Determine equivalence of languages accepted by Push Down Automata and languages generated by
context free grammars.
CO5:
Distinguish between computability and non-computability and Decidability& un-decidability.

Section – A (2×4 = 8)

What is the difference between acceptance of string in PDA with null stack or with
1. CO3
final state? 2
2. CO1
What is context Sensitive grammar. 2
3 Compare the computational powers of Pushdown Automata and Turing Machines. 2 CO3

4. Give instantaneous description of turing machine. 2 CO1


Section – B (2×4 = 8)
5
Explain NDPDA and DPDA with the help of example. 2+2=4 CO4
.
6
Explain the closure properties of Context free grammars. 1+1+1+1=4 CO3
.
7
Explain pumping lemma for Context free languages with the help of example. 4 CO3
.
Section – C (1×8 = 8)

8. Design a PDA which recognizes the set of all even length palindromes over {a,b}. 8 CO4

What are Turing machines? Explain different ways by which we can represent the
9. 4+4=8
Turing machines. CO5

You might also like