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.  Define finite automata. Give the formal definition of deterministic finite automata with example.

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

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

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

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

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

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

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

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

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

1.  Explain the extended transition function of NFA.

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. GIve the DFA accepting the string over {a, b} such that each string doesn't start with ab.

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

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.  Differentiate DFA with NFA. Design an NFA  accepting strings over {0, 1} that end in 01.

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.  How can you convert an ɛ-NFA into equivalent DFA? Explain.

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

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

3.  Give formal notation for an ε-NFA with 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.  What is finite automata? Describe its different variations with suitable examples.

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

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.  Convert the following NFA into equivalent DFA.

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

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

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

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

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.  How a NFA can be converted into a DFA? Convert the following NFA into equivalent DFA.

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

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

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

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.  Show that language of palindrome over {a,b} is not a regular language.

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

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.  Construct FA recognizing the languages described by following regular expressions.

        a)    (10*+01*)11*

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

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.

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.  Define Turing Machines.  Draw NFA - ε corresponding to following regular expression over  ∑ = {0,1} 

                    010* + 0(01+10)* 11

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.  What are the regular operators applied to the regular languages? Explain with example.

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

a) (11 + 10)^*01

b) (111 + 100)*10

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.

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.

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.

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

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

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

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.

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

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

                           ii. 001*0*11

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 the pumping lemma for regular language. Explain about its application.

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 CFG in CNF? What are the criteria to be a CFG in CNF? Explain.

4.  Convert following regular grammar into Finite Automata.

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

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

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

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

5.  Given the following grammar

        Remove the immediate left recursion from the grammar.

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

            S→ ABa,    A→ aab,    B→ AC

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. Convert the following CFG into Chomsky Normal Form.

S → |Sbb|aabb|Aa|Bb,

A → Aa|a,

B → Bb|b|ɛ

11.  Convert the following grammar into Chomsky Normal Form.

            S→ ASB|ε

            A →aAS|bAS|a

            B→SbS|A|CS|bb

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 Context Free Grammar. Given the following CFG.

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

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

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.

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

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.  Give the formal definition of NPDA. How it differs with DPDA? Explain.

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

5. Convert following grammar into equivalent PDA

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

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

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

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

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.  Construct a PDA that accepts the strings of language L={ ww^R | w is in {a, b}*}.

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

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

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 deterministic PDA. Design a PDA that accept a language L = {anbn | n>0}. You may accept either by empty stack or 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.

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.

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

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

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.  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 Turing machine. What are the roles of Turing machines?

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

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

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

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

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

7.  What is a universal Turing machine?

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

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.  Describe the Turing machine. Construct a TM that accepts even length strings from alphabet {0, 1}.

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

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

8.  What is universal language? Explain.

8.  What is recursive language? Explain.

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.  Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement.    (1+4)

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

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.  How can you show that the one tape Turing machine and multi-tape Turing machine are equivalent? Explain in detail.

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.  Describe a Universal Turing Machine and its operations. What types of languages are accepted by Universal TM?

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.

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

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

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.

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

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.  Differentiate between class P and class NP.

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

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

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

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

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

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 (Any two):

        a) Solvable vs Unsolvable problems

        b) CNF Satisfiability

        c) Recursive and Recursively Enumerable Languages

14.  Write short notes on:

a.               Decidable Vs Un-decidable problems.

b.              Unrestricted Grammar

c.               NP-completeness

d.              CNF-SAT Problem.

14.  Write short notes on:

        a) Turing maching

        b) Classes P and NP

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)       Unrestricted Grammar

b)       Universal Turing Machine

c)       CNF-SAT problem Complexity