# Theory of Computation (Test 4)

## Gate Exam : Cs Computer Science And Information Technology

| Home | | Gate Exam | | Cs Computer Science And Information Technology | | Theory of Computation |

Theory of Computation
| Theory of Computation |
Q.1
What is the complement of the language accepted by the NFA show below? Assume Σ ={a} and ε is the empty string.

A.
B. {ε}
C. a *
D. {a, ε}
Explaination / Solution:

Language accepted by NFA is a+ , so complement of this language is {є}

Workspace
Report
Q.2
What is the correct translation of the following statement into mathematical logic? “Some real numbers are rational”
A. ∃x (real(x) v rational (x))
B. ∀x (real(x)→rational (x))
C. ∃x (real(x)∧ rational (x))
D. ∃x (real(x)∧ rational (x))
Explaination / Solution:

Option A: There exists x which is either real or rational and can be both. Option B: All real numbers are rational Option C: There exists a real number which is rational. Option D: There exists some number which is not rational or which is real.

Workspace
Report
Q.3
If G is grammar with productions S → SaS|aSb|bSa|SS|∈ where S is the start variable, then which one of the following is not generated by G?
A. abab
B. aaab
C. abbaa
D. babba
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
Consider the following languages over the alphabet ∑= {a, b,c}

Which of the following are context-free languages ?
I. L∪ L2                  II. L1 ∩ L2
A. I only
B. II only
C. I and II
D. Neither I nor II
Explaination / Solution:

Workspace
Report
Q.5
Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* . We say f is computable if there exists a Turning machine M which given an input x in A* , always halts with f(x) on its tape. Let Lf denote the language {x#f(x)|x∈A*}. Which of the following statements is true:
A. f if computable if and only if Lf is recursive
B. f is computable if and only Lf recursively enumerable.
C.  If f is computable then Lf is recursive, but not conversely.
D. If f is computable then Lf is recursively enumerable, but not conversely.
Explaination / Solution:

A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.

Workspace
Report
Q.6
Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are nonterminals
G1 : S → aSb|T,T → cT|∈
G2 : S → bSa|T,T → cT|∈
The language L(G1) ∩ L(G2) is
A. Finite.
B. Not finite but regular
C. Context-free but not regular.
D. Recursive but not context-free.
Explaination / Solution:

The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals are:

Workspace
Report
Q.7
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
A. L2 – L1 is recursively enumerable
B. L1 – L3 is recursively enumerable
C. L2 ∩ L1 is recursively enumerable
D. L2 ∪ L1 is recursively enumerable
Explaination / Solution:
No Explaination.

Workspace
Report
Q.8
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, \$ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S

The First and Follow sets for the non-terminals A and B are
A.  FIRST(A) = {a, b, ε } = FIRST (B)
FOLLOW(A) = {a, b}
FOLLOW(B) = {a, b, \$}
B. FIRST(A) = {a, b, \$}
FIRST(B) = {a, b, ε }
FOLLOW(A) = {a, b}
FOLLOW(B) ={\$}
C.  FIRST(A) = {a, b, ε } = FIRST(B)
FIRST(A) = {a, b}
FOLLOW(B) = ∅
D. FIRST(A) = {a, b,} = FIRST(B)
FIRST(A) = {a, b}
FOLLOW(B) ={a, b}
Explaination / Solution:

Workspace
Report
Q.9
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, \$ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The appropriate entries for E1, E2, and E3 are
A. E1: S →aAbB, A →S
E2: S →bAaB, B → S
E3: B →S
B. E1: S →aAbB, S → ε
E2: S →bAaB, S → ε
E3: S → ε
C. E1: S →aAbB, S → ε
E2: S →bAaB, S → ε
E3: B →S
D. E1: A →S, S→ ε
E2: B →S, S → ε
E3: B →S
Explaination / Solution:

Workspace
Report
Q.10
The grammar S → aSa|bS|c is
A. LL(1) but not LR(1)
B. LR(1) but not LR(1)
C. Both LL(1) and LR(1)
D. Neither LL(1) nor LR(1)