CS-501 - Theory of Computation

What is a DFA machine? Design a deterministic finite automata machine over the alphabet set {0, 1}, accepting all strings starting and ending with different alphabet. [8 Marks]

Define finite-automata machine mathematically and explain its types. [6 Marks]

Consider the following grammar for list structures: S $\to$ a/$A$ T $\to$ T,S Find left most derivation, right most derivation and parse tree for the string ((a,a),a). [6 Marks]

Write the differences between Mealy and Moore machine. Convert the given Moore machine into its equivalent Mealy machine. alt='' [8 Marks]

Discuss about the Chomsky hierarchy of languages with their grammar constraints rules and corresponding automata for each class. [8 Marks]

Define the regular expression. Find the regular expression for the given DFA machine. alt='' [6 Marks]

Find a reduced Grammar equivalent to Grammar G, having Production rules P: P: {S $\to$ AC/B, A $\to$ a, C $\to$ c/BC, E $\to$ aA/c} [8 Marks]

Construct the PDA accepting the language { (ab)^n : n $\ge$ 1 } by empty stack. [6 Marks]

Minimize the DFA using Myhill-Nerode Theorem. alt='' [8 Marks]

Explain the different models of the Turing machines. [6 Marks]

Show that L = {a^nb^nc^n | n $\ge$ 1} is not a context-free language. [8 Marks]

Explain the difference between tractable and intractable problems with examples. [7 Marks]

Is NPDA (non-deterministic PDA) and DPDA (deterministic PDA) equivalent or not? Illustrate with an example. [7 Marks]

Explain P and NP problems with examples. [4 Marks]

Write a short notes on the following:

i) Universal Turing machine

ii) Post Correspondence Problem [10 Marks]