Theory Of Automata Formal Languages (KCA-201) - AKTU Question Paper 2021-22
MCA · Semester 2 · Free PDF Download
This is the official AKTU Theory Of Automata Formal Languages Previous Year Question Paper for MCA Semester 2, academic session 2021-22. Published by Dr. A.P.J. Abdul Kalam Technical University (AKTU/UPTU), Lucknow. Free PDF download — no login required.
Course:MCA
Semester:Semester 2
Session:2021-22
University:AKTU / UPTU
Rate this paper
Questions Asked in 2021-22
Theory Of Automata Formal Languages (KCA-201) — extracted question text
Section AAttempt all q u e s t i o n s i n b r i e f . 2*10 = 20
- aDefine alphabets and strings. 1
- bDifferentiate between dead sta te and not reachable states. 1
- cWhat is Kleen Closure? 2
- dWhat do you mean by ambiguous grammar? 2
- eWhat is Useless Production i s Context Free Grammar (CFG)? 3
- fDiscuss the rules for Ch omsky Normal Form (CNF). 3
- gWhat is an Instantaneous description in Push Down Automata (PDA)? 4
- hWhat is the problem associated with Finite Automata and how Push Down Automata (PDA) resolved it? (i) Discuss Universal Turing Machine. 5 (j) What is Halting Problem in Turing Machine. 5
Section BAttempt any three o f t h e f o l l o w i n g : 10*3 = 30
- aDesign the Deterministic Finite Automata (DFA) over the inp ut ∑= {0,1} that will accept the following languages. (i) The set of all strings having length 7. Provided that 2nd digit from left is 1 and 3rd digit from right is 0. (ii) Set of all strings containing 111 as sub string
- bWrite the regular expression for the following (with explanation) having input symbols {0,1}* (i) The language of all strings containing at least two 0’s. (ii) The language of all strings which starts and ends with same digits. (iii) The language of all strings containing 101 or 010 as sub strings. (iv) The language of all strings containing at most two 1’s
- cDefine the syntax tree. Productions of a grammar ‘G’ are defined as: A → a | aS | bAA B → b | bS | aBB. For the string aaabbabbba, (a) the leftmost derivation, (b) the rightmost derivation. (c) Derivation tree
- dHow two stack PDA differs f rom one stack PDA. Explain two stack PDA with suitable example
- eDefine Post Corresponding Problem (PCP)? Check does PCP wit h two lists X= (0101, 000111, 001, 10, 01, 00) and Y= (0101000, 11, 1 001, 100, 10, 0) have a solution?
Section CAttempt any one p a r t o f t h e f o l l o w i n g : 10*1 = 10
- aConstruct the Moore Machines that will count occurrences of substring ‘ab’ over the input ∑ = {a, b} and convert into Mealy Machine. What is need minimization of DFA? Minimize the given DFA
- aWhat is regular Expression? Using Arden’s Theorem, convert the given transition diagram into regular expression
- bState Pumping Lemma. Check t he strings accepted by Language L = {an bn | n ≥ 0} are regular or not?
- aDefine grammar. Construct a grammar G for: (i) Set of odd length palindromes over input {0, 1}. (ii) L(G) = {w ε {a. b} | w has an equal number of a's and
- bWhat is the Chomsky hierarchy of languages? 3
- aWrite the formal definition of Push Down Automata (PDA). Co nstruct
- aPDA that accepts language L = {wcwr such that w ε (a, b) *}
- bDifferentiate between deterministic and non-deterministic P DA. 4
- aWhat do you mean by Truing Machine? Design a Turing Machine that will accept all string specified the language L = {anbn, n≥1}
- bWrite the short note on: (i) Multi-Tape and Multi-Head Turing Machine (ii) Church-Turing Thesis
Question text is extracted from the official AKTU question paper PDF above. Check the original PDF for equations, diagrams and complete wording. Extracted: 2026-08-23.
Theory Of Automata Formal Languages — Other Year Papers
AKTU Theory Of Automata Formal Languages PYQs from other sessions
More MCA Semester 2 (2021-22) Papers
Other subjects from same semester and session
Cyber Security2021-22Data Structures Analysis Of Algorithms2021-22Database Management Systems2021-22Object Oriented Programming2021-22Operating Systems2021-22
View all MCA Semester 2 2021-22 papers →