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

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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

**Answer : ****Option D**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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

**Answer : ****Option C**

**Explaination / Solution: **

2^{ε*} is the power set of ε *

2

ε * is countabily infinite.

The power set of countabily infinite set is uncountable.

So 2^{ε*} is uncountable, and ε * is countable

Workspace

Report

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.

**Answer : ****Option A**

**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.

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

Consider the following languages over the alphabet Σ = {0,1,c}

For the languages L

Workspace

Report

Let L = L_{1} ∩ L_{2}, where L_{1} and L_{2 }are languages as defined below:

**A. ** Not recursive

**B. ** regular

**C. ** context – free but not regular

**D. ** recursively enumerable but not context-free

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

Then L is

No Explaination.

Workspace

Report

Consider two transactions T_{1} and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below:

**A. ** S1 and S2

**B. ** S2 and S3

**C. ** S3 only

**D. ** S4 only

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

Which of the above sche dules are conflict-serializable?

No Explaination.

Workspace

Report

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

**Answer : ****Option C**

**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.

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

If the difference between the expectation of the square of random variable (E[X^{2}]) and the square of the expectation of the random variable (E[X^{2}]) is denoted by R then

**A. ** R = 0

**B. ** R<0

**C. ** R ≥ 0

**D. ** R>0

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report