Q147: Regular expression of string having length at least 3 and third symbol as 0

Question 147: What is the regular expression of the language {w| w has length at least 3 and its third symbol is a 0}?

1. ΣΣ0Σ
2. ΣΣ0Σ*
3. Σ* Σ* 0 Σ
4. None of the above

Solution: The correct answer is option 2. The regular expression in option 1 will have exactly 4 length strings. Option 3 might have no symbols before 0 because * denotes 0 or more occurrences. Option 2 has exactly two symbols from its alphabet and third symbol is always 0, followed by any number of any symbol from alphabet.

Q66: Unrestricted grammar

Given the following unrestricted grammar,

 

Question 66: What are the transitions involved in derivation of ‘abc’?

1. S -> ABCS -> ABCZ -> ABZc -> AXbc -> Xabc -> abc
2. S -> ABCS -> ABCZ -> ABYc -> AYbc -> Xabc -> abc
3. S -> ABCS -> ABCZ -> ABYc -> AXbc -> Xabc -> abc
4. S -> ABCS -> ABCZ -> ABYc -> AXbc -> abc

 

Solution:

We can follow the transitions to see that other options are wrong. The correct answer is option 3.

Q33: Recursive & RE languages

Question #33: What is true about recursive and recursive enumerable languages?

Options:
A) A language L is recursively enumerable if L = L(M) for some Turing machine M.

B) Recursive languages are those languages that are not only recursively enumerable, but are also accepted by a TM that always halts, regardless of whether or not it accepts.

C) A language L is recursive if L = L(M) for some Turing machine M.

D) Both A and B.

Solution: Recursive languages are subset of recursively enumerable languages. Recursive enumerable languages can have a TM but there is no guarantee that the TM will eventually halt. Hence, correct answer is C.