Download DBATU B.Tech 2019 Oct-Nov CSE 5th Sem Theory Of Computation Question Paper

Course: B. Tech in Computer Sci. & Engineering

Subject Name: Theory of Computation

Max Marks: 20

--- Content provided by FirstRanker.com ---

Instructions to the Students:

1. Figures to the right indicate marks.
2. Assume suitable data.

Q. 1 Select the correct option.

1. _______is a set of strings.
   1. Language

   --- Content provided by FirstRanker.com ---

   2. grammar
   3. NFA
   4. DFA
2. Let r and s are regular expressions denoting the languages R and S. Then (rs) denotes
   1. RS

   --- Content provided by FirstRanker.com ---

   2. R*
   3. RUS
   4. R+
3. In transition diagrams a state pointed by an arrow represents the _______state.
   1. final

   --- Content provided by FirstRanker.com ---

   2. interior
   3. start
   4. final or start
4. _______grammar is also known as Type 3 grammar.
   1. unrestricted

   --- Content provided by FirstRanker.com ---

   2. context free
   3. context sensitive
   4. regular grammar
5. Grammar that produce more than one Parse tree for same sentence is:
   1. Ambiguous

   --- Content provided by FirstRanker.com ---

   2. Unambiguous
   3. Complementation
   4. Intersection
6. S → Sab Sa _______is which grammar?
   1. Right Linear Grammar

   --- Content provided by FirstRanker.com ---

   2. Left Linear Grammar
   3. Linear Grammar
   4. None of the above

Q.2 Solve Any Two of the following.

--- Content provided by FirstRanker.com ---

1. Construct the DFA (∑ = 0,1)
   1. w= Strings starting and ending with same characters
   2. w= string with "101" as substring
2. Consider following Grammar:
   S→ A1B
   

   --- Content provided by FirstRanker.com ---

   A→ OA | epsilon
   B→1B|0B | epsilon
   Give the leftmost derivation for the inputs:
   1. 00101
   2. 1001

--- Content provided by FirstRanker.com ---

3. Construct the regular Grammar for the given finite Automata: FirstRanker.com

Q. 3 Solve Any One of the following.

1. What is pumping lemma technique? Using pumping lemma show that L= {a^n b^n | n>=1} is not regular language. FirstRanker.com
2. Convert Following NFA to DFA

   1. state	0	1
      → a	{a,b}	{a}
      b	{c}	{c}
      C	{d}
      * d	{d}	{d}

   2. state	0	1
      → p	{q,r}	{b]
      *q	{r}	{q,r}
      r	{s}	{p}
      *s	[d}

   --- Content provided by FirstRanker.com ---