CSIT-503 (A) - Theory of Computation

What are the components of finite automata model? Construct deterministic finite automata to recognize odd number of 1's and even number of 0's.

Convert the Regular expression $(a+b)^*abb$ directly into aDFA.

Consider the FA and construct regular expressions that are accepted by it. alt=''

Construct the PDA for the following grammar. $X \to 0X3$ $X \to 0A3$ $A \to 1A2$ $A \to 12$

Show id + id * id can be generated by two distinct leftmost derivative in the grammar. $E \to E+E / E*E / (E) / id.$

Can an ambiguous CFG be converted into Chomsky Normal Form. Explain briefly your answer.

Construct PDA for the language $L = \{a^nb^m c^n, \text{ where } n \ge 0, m \ge 0\}$.

Construct the PDA for the following grammar. $S \to aS | aSbS | \epsilon$

Design a TM to accept the string $L = (a,b)^*$, where $N(a)+N(b)=$ even.

Give the tuple definition of Turing machine and explain the significance of movement of R/W head.

Convert the following Mealy machine to an equivalent Moore machine by the tabular format.

Explain Chomsky hierarchy of grammar with suitable example.

Convert CFG to GNF $A \to BB/I$ $B \to AA/0$

Construct the context free grammar equivalent to a regular expression $(01+1)^* (00+1)$.

2-way Finite Automata

Properties of Regular Grammar

Multi Tape TM

Arden's Theorem