Dbms U4
Dbms U4
Dbms U4
2 Marks
1. State the difference between recursive and recursively enumerable languages.
A recursive language (subset of RE) can be decided by Turing machine which means it
will enter into final state for the strings of language and rejecting state for the strings
which are not part of the language. e.g.; L= {anbncn|n>=1} is recursive because we can
construct a turing machine which will move to final state if the string is of the form
anbncn else move to non-final state. So the TM will always halt in this case. REC
languages are also called as Turing decidable languages.
wi1,wi2,....,wim=xi1,xi2,....,xim.
The sequence i1,....,im is a solution to this instance of PCP.
MPCP
Lists A & B of k strings each from Sigma*.say
A=w1,w2,...,wk
and
B=x1,x2,.....,xk
does there exist a sequence of integers i1,i2,....,ir.
such that
w1 wi1 wi2 .... wir=x1 xi1 xi2 ..... xir ?
Difference between PCP and MPCP is that in the MPCP, a solution is required to start
with the first string on each list.
4. Define NP and give example
Computer scientists have studied many NP problems, that is, problems that can be
solved nondeterministically in polynomial time.
The Hamiltonian Path Problem
The Clique Problem
5. Define Space and Time Complexity
which is a rough measure of the time taken by a
particular computation. There are many results for space-complexity as well, but
time-complexity is a little more accessible and, at the same time, more useful.
Big Questions
1. Derive the Context sensitive grammar for The language L =
{anbncn: n ≥ 1} is a context-sensitive language. And demonstrate
with tracing.
More Examples:
2. Explain Chomsky Hierarchy and Give example for Each
3. Let A = {001, 0011,11,101} and B = {01, 111, 111, 010}. Does the
pair (A,B)have a PC solution? Does it have an MPC solution?
This instance of PCP has a solution if there is any sequence of integers i1,i2,.....,im,with
m>=1. Such that
wi1,wi2,....,wim=xi1,xi2,....,xim.
The sequence i1,....,im is a solution to this instance of PCP.
Example 1
Does PCP with two lists x = (b, a, aba, bb) and y = (ba, ba, ab, b) have a solution?
Solution: Now we have to find out such a sequence that strings formed by x and y are
identical. Such a sequence is 1, 2, 1, 3, 3, 4. Hence from x and y list
Obtain the solution for the following system of posts correspondence problem. A =
{100, 0, 1}, B = {1, 100, 00}
Solution: Consider the sequence 1, 3, 2. The string obtained from A = babababb. The
string obtained from B = bababbbb. These two strings are not equal. Thus if we try
various combination from both the sets to find the unique sequence, we could not get
such a sequence. Hence there is no solution for this system.
Satisfiable : If the Boolean variables can be assigned values such that the formula
turns out to be TRUE, then we say that the formula is satisfiable.
Unsatisfiable : If it is not possible to assign such values, then we say that the
formula is unsatisfiable.
To understand this better, first let us see what is Conjunctive Normal Form (CNF)
or also known as Product of Sums (POS).
CNF : CNF is a conjunction (AND) of clauses, where every clause is a disjunction
(OR).
Now, 2-SAT limits the problem of SAT to only those Boolean formula which are
expressed as a CNF with every clause having only 2 terms(also called 2-CNF).
S → S1B,
S1 → a S1b
bB → bbbB,
a S1b → aa
B→λ
Solution:
Possible Theorems from Unit IV ( 5 Theorems)