Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU)) B-Tech 4th Semester (Fourth Semester) 2018-19 RCS403 Theory Of Automata And Formal Languages Question Paper
| 14-May-2019 08:57:27 | 45.115.62.2
FirstRanker.com | 14-May-2019 08:57:27 | 45.115.62.2
RCS403
Page 1 of 2
Printed Pages: 02 Sub Code: RCS403
Paper Id: 110257 Roll No.
B TECH
(SEM-IV) THEORY EXAMINATION 2018-19
THEORY OF AUTOMATA AND FORMAL LANGUAGES
Time: 3 Hours Total Marks: 70
Note: Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. For the given language L1 = ?, L2 = {a}, L3 = ?. Compute L1
L2
*
U L3
*
.
b. Design a FA to accept the string that always ends with 101.
c. Write regular expression for set of all strings such that number of a?s divisible
by 3 over ? = {a,b}
d.
e.
f.
g.
Construct the CFG for the Language L = {a
2n
b
n
|n>=3}.
What do you mean by ?-Closure in FA?
Explain Universal TM.
Explain Two Stack PDA.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Construct a minimum state DFA from given FA
Fig. 1
b. Find the regular expression corresponding to the finite automata given bellow:
Fig. 2
P.T.O
FirstRanker.com - FirstRanker's Choice
FirstRanker.com
| 14-May-2019 08:57:27 | 45.115.62.2
FirstRanker.com | 14-May-2019 08:57:27 | 45.115.62.2
RCS403
Page 1 of 2
Printed Pages: 02 Sub Code: RCS403
Paper Id: 110257 Roll No.
B TECH
(SEM-IV) THEORY EXAMINATION 2018-19
THEORY OF AUTOMATA AND FORMAL LANGUAGES
Time: 3 Hours Total Marks: 70
Note: Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Attempt all questions in brief. 2 x 7 = 14
a. For the given language L1 = ?, L2 = {a}, L3 = ?. Compute L1
L2
*
U L3
*
.
b. Design a FA to accept the string that always ends with 101.
c. Write regular expression for set of all strings such that number of a?s divisible
by 3 over ? = {a,b}
d.
e.
f.
g.
Construct the CFG for the Language L = {a
2n
b
n
|n>=3}.
What do you mean by ?-Closure in FA?
Explain Universal TM.
Explain Two Stack PDA.
SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Construct a minimum state DFA from given FA
Fig. 1
b. Find the regular expression corresponding to the finite automata given bellow:
Fig. 2
P.T.O
FirstRanker.com
| 14-May-2019 08:57:27 | 45.115.62.2
FirstRanker.com | 14-May-2019 08:57:27 | 45.115.62.2
RCS403
Page 2 of 2
c. Convert the following CFG to its equivalent GNF:
S ? AA | a, A ? SS | b.
d. Design a PDA for the following language:
L = {a
i
b
j
c
k
| i = j or j = k}
e. Design a TM for the following language:
L = { a
n+2
b
n
| n >0 }
SECTION C
3. Attempt any one part of the following: 7 x 1 = 7
(a) Design FA for ternary number divisible by 5.
(b) Explain Myhill-Nerode Theorem using suitable example.
4. Attempt any one part of the following: 7 x 1 = 7
(a) Prove that the following Language L = {a
n
b
n
} is not regular
(b) Explain the Closure properties of regular expression.
5. Attempt any one part of the following: 7 x 1 = 7
(a) Design the CFG for the following language:
i) L = {0
m
1
n
| m ? n & m,n ? 1}
ii) L = {a
l
b
m
c
n
| l + m = n & l,m ? 1}
(b) Prove that the following Language L = {a
n
b
n
c
n
} is not Context Free.
6. Attempt any one part of the following: 7 x 1 = 7
(a) Design a PDA for the Language L ={WW
R
| W={a,b}
*
}
(b) Generate CFG for the given PDA M is defined as
M = ({q0, q1}, {0,1} {x, z0}, ?, q0, z0, q1) where ? is given as follows:
? (q0,1, z0) = (q0, xz0)
? (q0,1, x) = (q0, xx)
? (q0,0, x) = (q0, x)
? (q0, ?, x) = (q1, ?)
? (q1, ?, x) = (q1, ?)
? (q1,0, x) = (q1, xx)
? (q1,0, z0) = ( q1, ?)
7. Attempt any one part of the following: 7 x 1 = 7
(a) Design a TM for the following language:
L = { a
n
b
n
c
n
| n? 1}
(b) Write short note on:
i) Recursive Language and Recursively Enumerable Language.
ii) PCP problem and Modified PCP Problem
FirstRanker.com - FirstRanker's Choice
This post was last modified on 29 January 2020