[go: up one dir, main page]
Scribd
Upload
5 views4 pages

TOC Assignment

The document outlines two assignments related to automata theory and computation, with various tasks including designing DFAs, constructing finite automata, and defining closure properties. It also covers topics such as Turing machines, the halting problem, and conversions between Mealy and Moore machines. The assignments have specific submission deadlines and require the application of theoretical concepts in practical scenarios.

Uploaded by

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

TOC Assignment

The document outlines two assignments related to automata theory and computation, with various tasks including designing DFAs, constructing finite automata, and defining closure properties. It also covers topics such as Turing machines, the halting problem, and conversions between Mealy and Moore machines. The assignments have specific submission deadlines and require the application of theoretical concepts in practical scenarios.

Uploaded by

vanshikasehrawat1085
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

TOC Assignment-1 (Last Date of Submission 04.10.

2024)

1. Design an optimized DFA equivalent to NFA

M = ({p, q, r, s}, {0, 1}, δ, p, {q, s})

Where δ is given below:

δ(p,0)=q ​ δ(r,0)=s

δ(p,1)=(q, s) ​ δ(r,1)=φ

δ(q,0)=q ​ δ(s,0)=p

δ(q,1)=(p,r) ​ δ(s,1)=q

2. Construct finite automata for the following Regular expression ((a + b)* + a.b)*

3. Convert the following NFA to its equivalent DFA

4. Define ''E"-Closure. Find E-Closure of all the states of given NFA. Remove E-moves without
changing the acceptance.

5. Reduce the following grammar

6. Find the equivalent GNF for following grammar

7. Find regular expression for the finite automata M given below


8. Explain the closure properties of regular set

9. Construct PushDown Automata for the CFG

G = ({S}, {a, b}, {S -> aSa | bSb | a | b}, S)

and show Acceptance/Rejection of a string w, where, w = aabaa.

10. Design the pushdown automata for the language L= {W c Wr/W ϵ (a, b)* and Wr is reverse}.

11. Give and explain Closure Properties of Context Free Languages (CFL).

12. Construct PDA for L={ 0m+n 1m 0n | m, n>=0} using empty stack and final state.

13. Design push down automata (PDA) to accept the language

L={W WR| W belong to {a,b}*} using empty stack and final state.

14. Define instantaneous description of a PDA

15. Construct the push down automata for the language L

L= { x| x consists of equal numbers of a’s and b’s}

16. Construct a Push Down Automata for the following Context free Grammar. S → 0BB, B→ 0S | 1S |
0

TOC Assignment-2 (Last Date of Submission 04.12.2024)

1. Design TM to calculate multiplication of two integer number

2. Design TM to calculate proper Subtraction of two integer number

3. Show that halting problem of TM is Undecidable

4. Write short notes on:

• Universal TM
• Linear Bounded Automaton
• Church Turing Thesis

5. Design a TM to perform addition of two unary number

6. Explain Chomsky hierarchy with suitable example

7. Consider the following two lists & derive whether the following PCP has a solution or not.

8. Compute A (1, 1), A (2, 1), A (1, 2), A (2, 2) using Ackermann’s function.

9. Convert the following Mealy machine into an equivalent Moore machine.

10. Convert the following Mealy machine into an equivalent Moore machine.

11. Convert the following Moore machine into its equivalent Mealy machine.

12. Convert the given Moore machine into its equivalent Mealy machine.
Q a b Output(λ)

q0 q1 q0 0
q1 q1 q2 0

q2 q1 q0 1

13. Convert the given Moore machine into its equivalent Mealy machine.
Q a b Output(λ)

q0 q0 q1 0

q1 q2 q0 1

q2 q1 q2 2

14. Explain the properties of recursive enumerable grammar ​

You might also like