Theory Of Automata Formal Languages (KCA201) - AKTU Question Paper 2023-24
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 2023-24. 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:2023-24
University:AKTU / UPTU
Rate this paper
Questions Asked in 2023-24
Theory Of Automata Formal Languages (KCA201) — extracted question text · 100 marks · 3 Hours
Section AAttempt all questions in brief.
- aWhat do you mean by Formal languages? 2 1
- bWhat do mean by acceptability of string? 2 1
- cState the Kleen’s Theorem. 2 2
- dWrite down the Closure proper ties of Regular Languages. 2 2
- eDifferentiate Right Linear and Left Linear grammars. 2 3
- fWhat do you mean by simplification of CFG? 2 3
- gWhat do you mean by ambiguity in CFG? 2 4
- hDefine Nondeterministic Pushdown Automata. 2 4 i. Define Linear Bounded automata. 2 5 j. What do you mean by Halting Problem? 2 5
Section BAttempt any three of the following:
- aConvert the following Mealy machine into an equivalent Moore machine: Mealy Machine Transition Table State Output State Output
- bExplain the difference betwee n Regular and Non-Regular Langu ages with suitable examples
- cFind the derivation tree for the generating the 𝑠𝑡𝑟𝑖𝑛𝑔 11001010from the following grammar: 𝑆 → 1𝐵|0𝐴, 𝐴 →1 |1𝑆|0𝐴𝐴, 𝐵 → 0|0𝑆|1𝐵𝐵
- dConstruct the PDA to accept the following language
- eWhat do you mean by Non-deterministic Turing Machine. Also c onstruct a TM over ሼ𝑎, 𝑏ሽ 𝑤ℎ𝑖𝑐ℎ 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑎 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 𝑎𝑏𝑏
Section CAttempt any one part of the following:
- aCheck whether the 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝟎𝟎𝟏𝟎𝟏 𝒂𝒏𝒅 𝟏𝟏𝟎𝟎𝟏𝟎areaccepted or not by the following 𝐹𝐴
- bConvert the following 𝜀 െ 𝑁𝐹𝐴 𝑡𝑜 𝑎𝑛 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡 𝐷𝐹𝐴
- aState and prove Arden’s theorem. 10 2
- bConstruct an Finite Automata equivalent to the Regular expre ssion given by
- aConstruct CFG for the regular expression: 𝑅ൌ ሺ01 ሻ∗01∗ 10 3
- bGive the following CFG having 𝑆as start symbol, find an equivalent CFG with
- aProve that the language: 𝐿 ൌ൛𝑎మ
- bConstruct a PDA that accepts the language generated by the f ollowing grammar: 𝑆→𝑎 𝐵 , 𝐵→𝑏 𝐴 | 𝑏 𝐴→𝑎 𝐵
- aDesign a TM for a set of all 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤𝑖𝑡ℎ 𝑒𝑞𝑢𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎 𝑎𝑛𝑑 𝑏. 10 5
- bDefine recursive function. Prove that the function
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 (2023-24) Papers
Other subjects from same semester and session
Operating Systems2023-24Database Management Systems2023-24Cyber Security2023-24Object Oriented Programming2023-24Data Structures Analysis Of Algorithms2023-24
View all MCA Semester 2 2023-24 papers →