Theory of Computation - Unit Wise Questions

1.  Define the term: Kleene closure, union, concatenation and power of an alphabet with example.

2.  Define the term: alphabet, substring/Prefix/Suffix of a string with example.

4. Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.

1. Convert the following NFA-ε into equivalent NFA without ε.

1.  How can you represent a finite Automata? Explain.

1.  Define finite automata. Give the formal definition of deterministic finite automata with example.

1. Define finite Automata with ɛ moves.Is ɛ NFA has more computation power than DFA?

1.  What do you mean by finite automata?  Explain deterministic finite automata with example.

1. Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

1.  What is finite automata? Define DFA  with suitable example.

1.  What is DFA? How it differ with a NFA? Explain.

1.  Explain the extended transition function of NFA.

1.  Differentiate between deterministic and non-deterministic finite automata.

1.  Define DFA and explain how it differs from NFA.

2.  Differentiate DFA with NFA. Design an NFA  accepting strings over {0, 1} that end in 01.

2.  Give the DFA for language of strings over {0, 1} in which each strings end with 11.

2.  Explain the finite automata with Epsilon Transition.

2.  Give the DFA for language of strings over{a,b} where no two consecutive a’s occurred.

2. GIve the DFA accepting the string over {a, b} such that each string doesn't start with ab.

2.  Construct a DFA that accepts the strings over alphabet {0,1} with odd number of 0's and even number of 1's.

2.  Construct a DFA that accepts all the strings of alphabet {a, b} having each strings with even number of 0’s and even number of 1’s.

2.  Construct a DFA that accepts only the strings ab, abb and baa not more from {a, b}^*.

3.  Give formal notation for an ε-NFA with example.

3.  How can you convert an ɛ-NFA into equivalent DFA? Explain.

3.  What do you mean by ε-closure of a state in NFA with epsilon moves. Explain with an example.

3.  Define the ε-closure of a state of ε-NFA with an example.

4.  Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0's and even number of 1's.    (2+3)

8.  Compare FA, NFA and NFA- ε with illustration.

9.  Describe the extended transition function of a NFA. Construct a NFA accepting the language over {a, b}* with each strings containing three consecutive b's. Show by extended function that it accepts abbb.

9.  Show that a language L is accepted by some DFA if and only if L is accepted by some NFA.

9.  Convert the following NFA into equivalent DFA.

9.  Define finite automata and draw FA for the strings.

9.  Explain about sub-set construction method to convert a NFA into equivalent DFA with suitable example.

9.  What is finite automata? Describe its different variations with suitable examples.

9.  Design a constructive method to prove that the complement of the language accepted by an NFA is accepted by a DFA.

9.  How a ε-NFA can be converted into NFA and DFA? Explain with a suitable example.

9.  Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA.    (2+3)

10.  Convert the following NFA into equivalent DFA using subset construction and also show the transition diagram for this DFA.

10.  Describe the method of subset construction to convert a given NFA into equivalent DFA with suitable example.

10.  Prove that for any given NFA N accepting a language L there exists a DFA D such that L(N) = L(D). 

10.  How a NFA can be converted into a DFA? Convert the following NFA into equivalent DFA.

11.  Show that a language L is accepted by some DFA if and only if L is accepted by s.

11.  Define the non-deterministic finite automata (NFA) and write down recursive definition of for NFA.

1.  Define the NFA with ε-transition and ε-closure of a state. Show that for every regular expression r, representing a language L, there is ε-NFA accepting the same language. Also convert regular expression (a+b)*ab* into equivalent Finite Automata.    (2+6+2)

2. Find the regular expression describing following languages over alphabet {0, 1}*.

        a) The language all strings containing at least two 0's.

        b) The language of all strings containing both 00 and 010 as substring.

2.  What do you mean by pumping lemma for regular languages?

2. Find the minimum state DFA for the given DFA below.

3.  Find the regular expression corresponding to the following languages over {0, 1}^*.

a)       The language of all strings containing exactly two 0's.

b)       The language of all strings containing 00 or 101 as substrings.

3.  Show that language of palindrome over {a,b} is not a regular language.

3.  Give the regular expression for the following languages.

        a. L={SS ∈ {a, b}* and S starts with aa or b and does not contains substring bb.

        b. L={S|S ∈ {0, 1}* and 0 occurs in pairs if any and ends with 1.

3.  For a regular expression (a+b)*baa, construct ε-NFA.

3.  Construct FA recognizing the languages described by following regular expressions.

        a)    (10*+01*)11*

        b)    (0+1)*(01+1000)0*

4.  Give the regular expression for the following languages over alphabet {a, b}

        a. Set of all strings ending with substring ab.

        b. Set of all strings with 2^nd and 4^th symbol is b.

4.  Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.

4.  Write regular expression for the following regular languages.

        a) The set of strings over a alphabet {a, b} containing at least one 'a' and at least one 'b'.

        b) The set of strings over {0, 1} whose 5th symbol from right end is 1.

4.  Construct the FA recognizing the language corresponding to the following regular expressions.

a) (11 + 10)^*01

b) (111 + 100)*10

4.  What are the regular operators applied to the regular languages? Explain with example.

4.  Define Turing Machines.  Draw NFA - ε corresponding to following regular expression over  ∑ = {0,1} 

                    010* + 0(01+10)* 11

5.  State the pumping lemma for regular language. Show by example, how can you use it to prove that a language is not regular.

5.  Simplify the following regular expressions.

a.) 1*+1*0(ɛ+0+1)*ø

b.) ɛ+0+1+( ɛ+0+1)( ɛ+0+1)*( ɛ+0+1)

5. Give the regular expressions for the following language over alphabet{a,b},

    a. Set of all strings with substring bab ar abb

    b. Set of all strings whose 3^rd symbol is 'a' and 5^th symbol is 'b'

6. Show that L = {aⁿ | n is a prime number} is not a regular language.

6.  Give the regular expressions for following language over alphabet {0, 1}.    (2.5+2.5)

        a. Set of all strings with 2^nd symbol from right is 1.

        b. Set of all strings starting with 00 or 11 and ending with 10 or 01.

7.  Show that language L={0^m1^m | m>=1} is not a regular language.

10.  What do you mean by regular expressions? Explain with example of pumping lemma for regular  languages.

9.  Show that for any regular expression, there is a NFA that accepts the same language represented by r. Convert the regular expression (a+b) (aa+ba)* + ab(a+b)* bba into NFA.

9.  Convert the following regular expression into ε-NFA.

        a) 01*                    b) (0+1)01*                    c) 00+(0+1)*100*

9.  What are the algebraic rules for regular expressions? Also show that if L, M, N are any regular language then show that L(M U N) = L.M U L.N.

10.  For the following regular expression draw an ε- NFA  recognizing the corresponding languages.

                           i. (00 +1)*(10)*

                           ii. 001*0*11

10.  State and prove the pumping lemma for regular language. Explain about its application.

10.  How do you convert a regular expression to automata? Convert the regular expression (0+1)*1(0+1) to auatomata.

10. Find the minimum state DFA equivalent to the following  DFA.

10.  State and prove pumping lemma for regular language. Show by example how it can be used to prove a language is not a regular.

11.  Convert the following DFA into minimum-state equivalent DFA.

11.  Explain about the closure properties of regular languages. Show that for any regular languages L₁ and L₂, L₁∪L₂ is also regualr.

12.  What is a regular grammar? Explain with example, about the method of converting a regular grammar into equivalent Finite Automata.

13.  Prove that any regular language can be accepted by a finite automata with all details.

3.  Explain the closure properties of context free languages with example.

4.  Define the term parse tree, regular grammar, sequential form and ambiguous grammar.

4.  What do you mean by a CNF grammar? Convert following grammar in CNF.

S → AC|ɛ, A → aS|a, C → BC|aC|b.

4.  Convert following regular grammar into Finite Automata.

4.  What do you mean by a CFG in CNF? What are the criteria to be a CFG in CNF? Explain.

5.  What is CFG? Design CFG for palindromes with alphabets {0, 1}.

5.  What do you mean by a CNF grammar? Convert following grammar into CNF.

            S→ ABa,    A→ aab,    B→ AC

5.  Define the term Regular Grammar. What is the relation of Regular Grammar with other grammars? Explain.

5.  Given the following grammar

        Remove the immediate left recursion from the grammar.

6.  what do you mean by a CNF grammar? Convert the following grammar into CNF.

                    S→abSb | aa

5.  Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.    (2.5+2.5)

7.  what are unrestricted grammar? How they differ with CFG? Explain.

8.  Explain about the Unrestricted Grammar.

7. Explain about the Chomsky's Hierarchy about the language and grammars.

9. Convert the following grammar into Chomsky Normal Form.

        S → abSb | a | aAb

        A → bS | aAAb | ε

10.  Define the term immediate left recursion. How can you convert a grammar with immediate left recursion into equivalent grammar without left recursion? Remove left recursion from the following grammar.

11.  Define CFG. Prove the following CFG is ambiguous.

S→S+S | S*S | (S) | a

Write the unambiguous CFG for the above grammar.

11.  Define regular grammar. Show with suitable example that the language described by regular grammar are accepted by a finite automata.

11.  Define CFG. Convert the following CFG into Chomsky Normal Form.

S → |Sbb|aabb|Aa|Bb,

A → Aa|a,

B → Bb|b|ɛ

11.  Define Context Free Grammar. Given the following CFG.

S →0AS | 0, A → SIA| SS | 10

11.  Convert the following grammar into Chomsky Normal Form.

            S→ ASB|ε

            A →aAS|bAS|a

            B→SbS|A|CS|bb

12.  What do you mean by the Chomsky Hierarchy in the formal language theory? Explain in detail. 

12.  Given the following grammar,

S → AAC |

A → aAb | ab | ɛ

C → aC | a | ɛ

Simplify the grammar and convert it into equivalent grammar in CNF.

12.  Convert the following CFG into CNF.

13.  Give a detailed description of ambiguity in context free grammar.

14.  Explain about the Chomsky Hierarchy of the language.

2.  How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa.    (2+4+4)

3.  Explain the non-deterministic PDA with example.

4.  Differentiate between deterministic and non-deterministic PDA.

5. Convert following grammar into equivalent PDA

5.  Define Deterministic Push Down Automata. How it differs with a Finite Automata.

5.  Give the formal definition of NPDA. How it differs with DPDA? Explain.

6.  Explain the method to convert a given CFG into equivalent PDA.

6.  Construct a PDA accepting L={w | w has equal no. of a's and b's}.

6.  How can you convert a CFG into equivalent PDA? Explain with example.

6.  What is PDA? How is it different from finite automata?

8. Define a Push Down Automata. Construct a PDA that accept L = {aⁿbⁿ | n>=0}.

10.  Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and1s. Show by sequence of IDs that 0101 is accepted by this PDA.    (3+2)

11.  Give the formal definition of Push Down Automata. Construct a PDA accepting the language

L = {0ⁿ1ⁿ | n > 0}

11.  Construct a PDA that accepts the strings of language L={ ww^R | w is in {a, b}*}.

12.  Construct a Push Down Automata that accepts all the strings from alphabet {0, 1} with equal number of 0 and 1. Show that 0110 is accepted by this PDA and 01101 is not.

12.  Define the language of PDA that accepts by Final State. Explain how a PDA accepting empty stack can be converted into a PDA by final state.

12.  Define the language of PDA that accepts by Final state. Explain, how a PDA accepting by empty stack can be converted into a PDA final state.

12.  Define deterministic PDA. Design a PDA that accept a language L = {anbn | n>0}. You may accept either by empty stack or by final state.

13.  Construct a PDA that accepts a language of palindrome of even length from an alphabet {a,b}.

13.  Define PDA. Explain how a PDA accepting by empty stack is converted into equivalent PDA accepting same language by final state.

13.  Discuss the equivalent of PDA and CFG. Convert the grammar

           S→aAA

           A→aS|bS|a

        to a PDA that accepts the same language by empty stack.

3. Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recoginzed by Universal Turing Machine.

3.  Define a Turing machine. Construct a TM that accept L = {wcw^R | w∈(0, 1) and c is ε or 0 or 1. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID).    (2+6+2)

5.  Explain the non-deterministic Turing machines with example.

5.  Explain about recursive enumerable and recursive language.

6.  What is a multi track Turing Machine? How it differs with single track machine?

6.  Give formal definition of Turing Machine. Explain the roles of Turing Machine.

6.  Construct a Turning Machine that accepts a language of strings over (a, b) with each string of even length. Show how it accepts string abab.

6.  Define the universal Turing machine and describe its role.

6.  Define the Turing machine. What are the roles of Turing machines?

7.  Design a Turing machine that accepts the language {0ⁿ1ⁿ|n≥1} over {0, 1}.

7.  Construct a Turing Machine that accepts the language of palindrome over {a, b}* with each string of odd length.

7.  Give the formal definition of Turning Machine. How it differs from PDA?

7.  What is a universal Turing machine?

7.  What is a Turing Machine? Give formal definition. How it differ from FA?

7.  Describe the Turing machine. Construct a TM that accepts even length strings from alphabet {0, 1}.

7.  Construct a Turing machine that accepts the language of palindrome over {a,b}* with each strings of even length.

8.  What is universal language? Explain.

8.  What is an algorithm? Explain on the basis of Church Hypothesis.

8.  What is recursive language? Explain.

8.  Explain, how can you encode a Turing machine into universal language.

8.  What is the role of a Turing machine? Explain.

8.  Describe the Turing machines with multiple tape, multiple track and storage in state.    (5)

10. Define Turing Machine and explain its different variations.

11. What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine.

11.  Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement.    (1+4)

12.  Describe multi tape Turing machine. Show that multi-tape Turing machine and one tape Turing machines are equivalent.

12.  Draw Turing machine to accept palindromes over {a, b}.

12.  Draw Turing Machine (TM) to accept  palindromes over {a, b}. (Even as well as odd Palindromes).

13.  Describe a Universal Turing Machine and its operations. What types of languages are accepted by Universal TM?

13.  How can you show that the one tape Turing machine and multi-tape Turing machine are equivalent? Explain in detail.

13.  Define Turing Machine. Construct the Turing machine that accepts the languages

                L={aⁿbⁿ | n>=0}

13.  Explain about multi tape TM. Show that every language accepted by a multi-tape Turning Machine is also accepted by one tape Turning Machine.

13.  Explain about multi tape TM. Show that every language accepted by a multi-tape Turing Machine is also accepted by one tape Turing Machine.

14.  Explain the term Turing acceptable and Turing decidable. Show that if L is recursive language then complement of L is also recursive.

14.  What is Universal Turing machine? Explain about the working mechanism of Universal Turing machine for processing the binary code input for (T, w) where T is specific Turing machine and w is input to T.

14.  Show that a Turing Machine with one tape and a Turing Machine with multiple tape are equivalent.

6.  Explain the computational complexity with example.

7.  What do you mean by problem reduction? Also explain about NP-Completeness.

7.  Differentiate between class P and class NP.

7.  Show that the complement of a recursive language is recursive.

8.  What do you mean by tractable and intractable problems? Is intractable problems are solvable by Turing machine?

8.  Define the term Class P and Class NP with example.

8.  What do you mean by Intractability? Explain in brief.

8.  Differentiate between class P and class NP.

12. Explain the term Intractability. Is SAT problem is intractable? Justify.

12.  What do you mean by tractable and Intractable problems?Explain with reference to TM.    (5)

13.  Define class P and NP with example. Show that: If P₁ is NP complete and there is a polynomial time reduction of p₁ to P₂ then P₂ is NP-complete.

14.  Write short notes on:

        a) Turing maching

        b) Classes P and NP

14.  Write short notes on:

a.               Decidable Vs Un-decidable problems.

b.              Unrestricted Grammar

c.               NP-completeness

d.              CNF-SAT Problem.

14.  Explain the following terms.

(a)  Big Oh and Big Omega

(b) Class P and NP

(c)  CNF SAT Problem

(d)
Turing Decidable and Acceptable problems.

14.  Explain the following:

a)      Minimization of finite state machine

b)      Push down automata (PDA).

c)      Halting problems

d)      Computational complexity

14.  Explain the following:

a)      Regular Grammar

b)      Halting problem

c)      Chomsky hierarchy

d)      NP-complete Problem

14.  Write short notes on (Any two):

        a) Solvable vs Unsolvable problems

        b) CNF Satisfiability

        c) Recursive and Recursively Enumerable Languages

14.  Write short notes on (Any two):

a)       Unrestricted Grammar

b)       Universal Turing Machine

c)       CNF-SAT problem Complexity