Which of the following problems is undecidable?

1.	Which of the following problems is undecidable?
A.	Deciding if a given context-free grammar is ambiguous
B.	Deciding if a given string is generated by a given context-free grammar
C.	Deciding if the language generated by a given context-free grammar is empty
D.	Deciding if the language generated by a given context-free grammar is finite
Answer» B. Deciding if a given string is generated by a given context-free grammar

Discussion

No Comment Found

Related MCQs

Let X denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q: F(P, Q) = ( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) ) The equivalent expression for F is
Consider the following relational schema: employee(empId, empName, empDept) customer(custId, custName, salesRepId, rating) salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return? SELECT empName FROM employee E WHERE NOT EXISTS (SELECT custId FROM customer C WHERE C.salesRepId = E.empId AND C.rating <> `GOOD`);
Consider the set of all functions f: {0,1, … ,2014} → {0,1, … ,2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements: P. For each such function it must be the case that for every i, f(i) = i. Q. For each such function it must be the case that for some i, f(i) = i. R. Each such function must be onto. Which one of the following is CORRECT?
Let d denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with d ≥ 3, which one of the following is TRUE?
If G is a forest with n vertices and k connected components, how many edges does G have?
There are two elements x, y in a group (G,∗) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that x ∗ x = y ∗ y = x ∗ y ∗ x ∗ y = y ∗ x ∗ y ∗ x = e where e is the identity element. The maximum number of elements in such a group is
Let S be the sample space and two mutually exclusive events A and B be such that A U B = S. If P(.) denotes the probability of the event. The maximum value of P(A)P(B) is ______
The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10 nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. The cache hit-ratio is 0.9. The average memory access time (in nanoseconds) in executing the sequence of instructions is __________.
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return -1; } Which one of the following statements about the function ProcessArray is CORRECT?

Which of the following problems is undecidable?

Discussion

No Comment Found

Related MCQs

Reply to Comment