Computer science: Theory Of computation MCQs

The following finite state machine accepts all those binary strings in which the number of 1’s and 0’s are respectively

The language {ambncm+n|m,n>=1} is

Consider the following grammar G:

S →bS | aA | b

A →bA | aB

B →bB | aS | a

Let Na( w) and Nb(w ) denote the number of a’s and b’s in a string w respectively. The language L(G) ⊆ {a,b}+ generated by G is

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, … define another language L2 over Σ ∪{#} as {wi#wj : wi,wj L1,i<j

}. Here # is a new symbol. Consider the following assertions.

S1: L1 is recursive implies L2 is recursive
S2: L2 is recursive implies L1 is recursive

Which of the following statements is true?

Consider three decision problems P1 ,P2 and P3 . It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?