Tribhuvan University

Institute of Science and Technology

2076

Bachelor Level / fourth-semester / Science

Computer Science and Information Technology (CSC257)

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

Attempt any Two questions. (2x10=20)

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 the regular expression (a+b)*ab* into an equivalent Finite Automaton.
How can you define the language accepted by a PDA? Explain how a PDA accepting a language by an empty stack is converted into an equivalent PDA accepting by the final state and vice-versa.
Define a Turing machine. Construct a TM that accepts L = {wcwR | w∈(0, 1) and c is ε or 0 or 1. Show that the string 0110 is accepted by this TM with the sequence of Instantaneous Description (ID).

Attempt any Eight questions. (8x5=40)

Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with an even number of 0’s and an even number of 1’s.
Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.
Give the regular expressions for the following language over the alphabet {0, 1}.
- Set of all strings with the 2nd symbol from the right is 1.
- Set of all strings starting with 00 or 11 and ending with 10 or 01.
Show that the language L={0m1m | m>=1} is not a regular language.
Describe the Turing machines with multiple tape, multiple track, and storage in state.
Construct an NFA accepting the language of {0, 1} with each string ending with 01 and convert it into an equivalent DFA.
Construct a PDA accepting the language over {0, 1} representing strings with an equal number of 0s and 1s. Show by the sequence of IDs that 0101 is accepted by this PDA.
Define the complexity of a Turing machine. Explain about big Oh, big Omega, and big Theta notation used for complexity measurement.
What do you mean by tractable and Intractable problems? Explain with reference to TM.