Hall Ticket No: Question Paper Code: A3513
VARDHAMAN COLLEGE OF ENGINEERING
(AUTONOMOUS) B. Tech IV Semester Regular/Supplementary Examinations, May 2018
(Regulations: VCE-R15) FORMAL LANGUAGE AND AUTOMATA THEORY
(Common to Computer Science and Engineering Information Technology) Date: 15 May, 2018 FN Time: 3 hours Max Marks: 75
Answer ONE question from each Unit
All Questions Carry Equal Marks
Unit I
1. Design Deterministic Finite Automata accepts all strings without two consecutive
over an alphabet 1}.
6M
Convert the following Nondeterministic Finite Automata to Deterministic Finite
Automata (DFA).
Fig.1
9M
2. Illustrate what does the given NFA accept.
Fig.2
5M
Design Deterministic Finite Automata for the following languages, over the
alphabet
i. Set of all strings containing the substring 0110
ii. Set of all strings that do not contain the substring 1010
10M
Unit II
3. Write regular expressions for the following languages over the alphabet Σ
i. All strings that do not end with aa
ii. All strings that contain an even number of
iii. All strings which do not contain the substring ba
iv. The language of all words
v. All words ending with b
vi. All words that start with a
vii. The language of all strings, not beginning with b
viii. All words that start with a double letter
8M
Prove the language L n is a square} is not regular by applying pumping lemma.
7M
4. Prove the language L over that contains 01 or 10 as sub-string is regular. 7M
Construct Regular Expression for the given DFA.
Fig.3
8M
Cont…2
2
Unit III
5.
Explain the two major normal forms for context-free grammar.
7M
Given the grammar G R aB bA,
A a
B aBB bS
i. Show a leftmost derivation of the string aaabbabbba
ii. Show a rightmost derivation of the string aaabbabbba
8M
6.
Construct a context-free grammar for strings over with exactly twice as many "a"s as "b"s.
7M
Consider the following language L {wwR w € Give a context-free grammar G that generates L and a parse tree that shows that aababb ∈ L.
8M
Unit IV
7.
Define the pushdown automata for language {anbn n 0}.
7M
Write the Algorithm to find PDA corresponding to a given CFG.
Construct a PDA from the following S)where the productions are −S → XS ε A → aXb Ab ab.
8M
8.
Construct the Deterministic Push Down Automata for anbncm m≥1.
8M
Construct a PDA that accepts L wwR w
7M
Unit V
9.
Find out whether "Is a number prime?" decidable or not.
7M
Consider a Turing machine with start state 0 and the following transitions:
State
Symbol
Symbol) 0
a
0
b
0

1
a
1
b
1

2
a
2

3
a
3
b
3

4
a
4
b
4

5
b
5

Trace the execution of this Turing machine with the stringbaaab#as input.
8M
10.
Design a Turing machine that transforms a string containing only and by replacing each letter preceding an to The Turing machine should always eventually enter an accepting state to terminate.
7M
Describe what is meant by each of the following:
i. Recursive languages
ii. Recursively enumerable languages
iii. Chomsky hierarchy
8M