Scribd
Upload
4 views2 pages

Theoretical Computer Science Assignments

The document outlines a series of assignments focused on theoretical computer science topics, including finite automata, regular expressions, context-free grammars, pushdown automata, and Turing machines. Each assignment consists of multiple questions that require explanations, examples, and discussions on applications and limitations of various computational models. Key concepts such as the Chomsky hierarchy, pumping lemma, and decidability are also addressed.

Uploaded by

Umar Nachan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views2 pages

Theoretical Computer Science Assignments

The document outlines a series of assignments focused on theoretical computer science topics, including finite automata, regular expressions, context-free grammars, pushdown automata, and Turing machines. Each assignment consists of multiple questions that require explanations, examples, and discussions on applications and limitations of various computational models. Key concepts such as the Chomsky hierarchy, pumping lemma, and decidability are also addressed.

Uploaded by

Umar Nachan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Subject: Theoretical Computer Science

ASSIGNMENT: 01
Q 1: What is Finite Automata? State and explain FSM with example.
Q 2: Write and explain Alphabets, Strings, Languages, Closure properties and Finite Automata.
Q 3: Write the Applications and limitations of FA?
Q 4: What is NFA and DFA? Convert the NFA to DFA With example?
Q 5: Write short notes on Moore and Mealy machines? Convert the Moore and Mealy Machine
with example?

ASSIGNMENT: 02
Q 1: What is Regular Expression? Describe the RE Applications.
Q 2: State and explain Pumping lemma for RLs.
Q 3: Write the different Applications of RE.

ASSIGNMENT: 03
Q 1: Describe the Chomsky hierarchy with example.
Q 2: Write a CFG for the regular expression r = 0*1(0+1)*
Q 3: The grammar G is S aB | bA, A  a| aS | bAA, B b | bS | aBB Obtain parse tree for
the following string “aababb” and check if the grammar is ambiguous.

ASSIGNMENT: 04
Q 1: Discuss the different Application of PDA.
Q 2: Design Push Down Machine that accepts

Q 3: Differentiate between FA, PDA and TM.


Q 4: Explain Non-Deterministic PDA.
ASSIGNMENT: 05
Q 1: Explain Halting Problem of Turing Machine.
Q 2: Design the Turing Machine to accept the language given by a regular expression 0(0+1)*11
Q 3: Write Variants of Turing Machine.
Q 4: Desing a TM accepting all palindromes over {0,1}.
Q 5: Define and Design TM to accept.

Q 6: Construct TM to check well formedness of parenthesis.

ASSIGNMENT: 06
Q 1: Write Short Notes on:
a. Halting Problem,
b. Rice ‘s Theorem,
c. Post Correspondence Problem.
Q 2: Discuss on Recursive and Recursively Enumerable Languages with example.
Q 3: State and explain Decidability and Undecidability.

You might also like