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.
Rate this paper
Questions Asked in 2021-22
Theory Of Automata Formal Languages (KCA-201) — complete question paper
- 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
- 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?
- 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. Hindi translations are omitted — every question is printed in English in the original paper. Last verified: 2026-08-23.
Repeated Questions — KCA-201
Questions that appeared in more than one session, found by comparing 4 years of Theory Of Automata Formal Languages papers (2021-22, 2022-23, 2023-24, 2024-25)
What do you mean by ambiguous grammar? 2
Appeared in: 2021-22 · 2023-24
Write the short note on: (i) Multi-Tape and Multi-Head Turing Machine (ii) Church-Turing Thesis
Appeared in: 2021-22 · 2022-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