Scribd
Upload
8 views2 pages

CSE301 Theory of Computation Test 2022

This document outlines the structure and content of the Third CIA Test for the course CSE301: Theory of Computation, held in December 2022. It includes various topics such as Recursive Enumerable (RE) languages, Recursive languages (REC), and the differences between NDPA and DPDA. The test consists of multiple parts with questions worth varying marks, focusing on theoretical concepts in computation.

Uploaded by

127003028
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

CSE301 Theory of Computation Test 2022

This document outlines the structure and content of the Third CIA Test for the course CSE301: Theory of Computation, held in December 2022. It includes various topics such as Recursive Enumerable (RE) languages, Recursive languages (REC), and the differences between NDPA and DPDA. The test consists of multiple parts with questions worth varying marks, focusing on theoretical concepts in computation.

Uploaded by

127003028
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

School of Computing

Third CIA Test – December 2022


Course Code: CSE301
Course Name: THEORY OF
COMPUTATION 7. 10101101101 00 1101101110111011
Duration: 90 minutes Max Marks: 50
8. L1 = {anbncn ,n>=1}, L2= {an! ,n>=0}
PART A – Answer all the questions 10 x 2 = 20 Marks

1.
9. Recursive Enumerable (RE) or Type -0 Language

RE languages or type-0 languages are generated by type-0


2.
grammars. An RE language can be accepted or recognized
by Turing machine which means it will enter into final
state for the strings of language and may or may not enter
into rejecting state for the strings which are not part of the
language. It means TM can loop forever for the strings
which are not a part of the language. RE languages are
also called as Turing recognizable languages.
3.
S -> aS | bS | ∊
Recursive Language (REC)
4. 1. E→E+T
2. E→T A recursive language (subset of RE) can be decided by
3. T→T*F Turing machine which means it will enter into final state
4. T→F for the strings of language and rejecting state for the
5. F → id strings which are not part of the language. e.g.; L=
{anbncn|n>=1} is recursive because we can construct a
5. NDPA is more powerful than DPDA because we can add more transitions to it. turing machine which will move to final state if the string
It is possible for every language to add a transition. For some languages, we is of the form anbncn else move to non-final state. So the
can construct DPDA there exist an NPDA but there are some languages that TM will always halt in this case. REC languages are also
are accepted by NPDA but are not by DPDA. This is said to be powerful when
it accepts more sets of languages than other automata. (1m)
called as Turing decidable languages.
Example (1m)

6. If L is a context-free language for which there exists an unambiguous


grammar, then L is said to be unambiguous. If every grammar that generates L
is ambiguous, then the language is called inherently ambiguous.
10. 13.

PART B – Answer any two questions 2 x 10 = 20 Marks


11. DFA of (a+b)*abb

(5m)
Example for Each (5m)

PART C – Answer All the Questions 1 x 10 = 30 Marks


14. a

12.

(7m)
Trace (3m) b. Satisfiable.
x1  0, x2  1, x3  1

You might also like