# Topic: Theory of Computation (Test 1)

Topic: Theory of Computation
Q.1
S → a Sa| bSb| a| b The language generated by the above grammar over the alphabet {a, b} is the set of
A. All palindromes
B. All odd length palindromes
C. Strings that begin and end with the same symbol
D. All even length palindromes
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
Which one of the following languages over the alphabet {0, 1} is described by the regular expression: (0 + 1)* 0 (0 + 1)* 0(0 + 1)*?
A. The set of all strings containing the substring 00
B. The set of all strings containing at most two ’s
C. The set of all string containing at least two ’s
D. The set of all strings that begin and end with either 0 or 1
Explaination / Solution:
No Explaination.

Workspace
Report
Q.3
Which one of the following is FALSE?
A. There is a unique minimal DFA for every regular language
B. Every NFA can be converted to an equivalent PDA
C. Complement of every context-free language is recursive
D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ* . Which one of the following is TRUE?
A. Both 2Σ* and Σ * are countable
B. 2Σ* is countable Σ * is uncountable
C. 2Σ* is uncountable and Σ * is countable
D. Both 2Σ* and Σ * are uncountable
Explaination / Solution:

2ε* is the power set of ε *
ε * is countabily infinite.
The power set of countabily infinite set is uncountable.
So 2ε* is uncountable, and ε * is countable

Workspace
Report
Q.5
Which one 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.
Explaination / Solution:

There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG, so it is undecidable.

Workspace
Report
Q.6
Consider the following languages over the alphabet Σ = {0,1,c}

Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree languages?
A. None of the languages
B. Only L1
C. Only L1 and L2
D. All the three languages
Explaination / Solution:

For the languages L1 and L2 we can have deterministic push down automata, so they are DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3  is not a deterministic CFL.

Workspace
Report
Q.7
Let L = L1 ∩ L2, where L1 and Lare languages as defined below:

Then L is
A. Not recursive
B. regular
C. context – free but not regular
D. recursively enumerable but not context-free
Explaination / Solution:
No Explaination.

Workspace
Report
Q.8
Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below:

Which of the above sche dules are conflict-serializable?
A. S1 and S2
B. S2 and S3
C. S3 only
D. S4 only
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
Match the following:

A. P - 2, Q - 3, R - 1, S - 4
B. P - 2, Q - 1, R - 4, S - 3
C. P - 2, Q - 4, R - 1, S - 3
D. P - 2, Q - 3, R - 4, S - 1
Explaination / Solution:

Lemical Analyzer uses DFA to recognize the longest possible input sequence that makes up a token. Parser takes input in the form of tokens and usually builds a data structure in the form of parse tree. Here parse tree can be termed as a Production tree as parser uses production of the grammar to check whether generated tokens form a meaningful compression). Register allocation can be reduced to K-colouring problem where K is the number of registers available on the target architecture. Post order traversal of expression tree gives postfix notation for a given expression & this post fix notation can be evaluated using stack.

Workspace
Report
Q.10
If the difference between the expectation of the square of random variable (E[X2]) and the square of the expectation of the random variable (E[X2]) is denoted by R then
A. R = 0
B. R<0
C. R ≥ 0
D. R>0