For S &in; (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s &in; (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}.Which one of the following statements is true?(A) L is recursively enumerable, but not recursive(B) L is recursive, but not context-free(C) L is context-free, but not regular(D) L is regular

For S &in; (0 + 1) * let d(s) denote the decimal value of s (e.g. d(10

1.	For S &in; (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s &in; (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}.Which one of the following statements is true?(A) L is recursively enumerable, but not recursive(B) L is recursive, but not context-free(C) L is context-free, but not regular(D) L is regular
Answer»

Discussion

No Comment Found

Related InterviewSolutions

Consider the following grammar.S -> S * ES -> EE -> F + EE -> FF -> idConsider the following LR(0) items corresponding to the grammar above.(i) S -> S * .E(ii) E -> F. + E(iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?(A) (i) and (ii)(B) (ii) and (iii)(C) (i) and (iii)(D) None of the above
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)(A) n — 1(B) 2n — 2(C) nC2(D) 2
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:(A) Queue(B) Stack(C) Heap(D) B-Tree
A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?(A) 400(B) 500(C) 600(D) 700
In a binary max heap containing n numbers, the smallest element can be found in time(A) O(n)(B) O(Logn)(C) O(LogLogn)(D) O(1)
You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°?(A) A(B) B(C) C(D) D
Which one of the following in place sorting algorithms needs the minimum number of swaps?(A) Quick sort(B) Insertion sort(C) Selection sort(D) Heap sort
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.(A) log2n(B) n(C) 2n + 1(D) 2^n — 1
Consider the following C-program fragment in which i, j and n are integer variables.for (i = n, j = 0; i >0; i /= 2, j += i);Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?(A) val(j) = (logn)(B) vaI(j) = (sqrt(n))(C) val(j) = (n)(D) val(j) = (nlogn)(A) A(B) B(C) C(D) D
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?(A) R is NP-complete(B) R is NP-hard(C) Q is NP-complete(D) Q is NP-hard

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment