MCASemester 22023-24Theory Of Automata Formal LanguagesKCA201

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) — complete question paper · 100 marks · 3 Hours

Section AAttempt all questions in brief.

a
What do you mean by Formal languages? 2 1
b
What do mean by acceptability of string? 2 1
c
State the Kleen’s Theorem. 2 2
d
Write down the Closure proper ties of Regular Languages. 2 2
e
Differentiate Right Linear and Left Linear grammars. 2 3
f
What do you mean by simplification of CFG? 2 3
g
What do you mean by ambiguity in CFG? 2 4
h
Define 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:

a
Convert the following Mealy machine into an equivalent Moore machine: Mealy Machine Transition Table State Output State Output
b
Explain the difference betwee n Regular and Non-Regular Langu ages with suitable examples
c
Find the derivation tree for the generating the 𝑠𝑡𝑟𝑖𝑛𝑔 11001010from the following grammar: 𝑆 → 1𝐵|0𝐴, 𝐴 →1 |1𝑆|0𝐴𝐴, 𝐵 → 0|0𝑆|1𝐵𝐵
d
Construct the PDA to accept the following language
e
What do you mean by Non-deterministic Turing Machine. Also c onstruct a TM over ሼ𝑎, 𝑏ሽ 𝑤ℎ𝑖𝑐ℎ 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑎 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 𝑎𝑏𝑏

Section CAttempt any one part of the following:

a
Check whether the 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝟎𝟎𝟏𝟎𝟏 𝒂𝒏𝒅 𝟏𝟏𝟎𝟎𝟏𝟎areaccepted or not by the following 𝐹𝐴
b
Convert the following 𝜀 െ 𝑁𝐹𝐴 𝑡𝑜 𝑎𝑛 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡 𝐷𝐹𝐴
a
State and prove Arden’s theorem. 10 2
b
Construct an Finite Automata equivalent to the Regular expre ssion given by
a
Construct CFG for the regular expression: 𝑅ൌ ሺ0൅1 ሻ∗01∗ 10 3
b
Give the following CFG having 𝑆as start symbol, find an equivalent CFG with
a
Prove that the language: 𝐿 ൌ൛𝑎௜మ
b
Construct a PDA that accepts the language generated by the f ollowing grammar: 𝑆→𝑎 𝐵 , 𝐵→𝑏 𝐴 | 𝑏 𝐴→𝑎 𝐵
a
Design a TM for a set of all 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤𝑖𝑡ℎ 𝑒𝑞𝑢𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎 𝑎𝑛𝑑 𝑏. 10 5
b
Define recursive function. Prove that the function

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 — KCA201

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)

Write down the Closure proper ties of Regular Languages. 2 2

Appeared in: 2023-24 · 2024-25

What do you mean by ambiguity in CFG? 2 4

Appeared in: 2021-22 · 2023-24

Theory Of Automata Formal Languages — Other Year Papers

AKTU Theory Of Automata Formal Languages PYQs from other sessions

Theory Of Automata Formal Languages2021-22 Theory Of Automata Formal Languages2022-23 Theory Of Automata Formal Languages2024-25

More MCA Semester 2 (2023-24) Papers

Other subjects from same semester and session

Operating Systems2023-24 Database Management Systems2023-24 Cyber Security2023-24 Object Oriented Programming2023-24 Data Structures Analysis Of Algorithms2023-24

View all MCA Semester 2 2023-24 papers →