THEORY OF COMPUTATION MCQ QUESTIONS:
Which of the following statements is/are false? *
| | The class of languages accepted by PDA's are closed under complementation. |
| | NDPDA is more powerful than DPDA. |
| | If L is a context free language, then there exists a DPDA accepting L. |
| | If a Context free grammar G is ambiguous, then it necessarily implies that L(G) is also ambiguous. |
Which of the following statements is/are true? *
| | The language L = { ww | w is in (0+1)* } is a Context free language. |
| | Presence of unit-production in a Context free grammar increases the cost of derivation. |
| | Presence of lemda-production in a Context free grammar G, necessarily implies that L(G) contains null string. |
| | If G is a Context free grammar, then for some w in L(G), there may exists only one leftmost derivation, but more than one rightmost derivations. |
Let G = ({S}, {a,b}, P, S) be a Context free grammar where the rule set P is : S --> aSb ; S --> SS and S --> lemda. Which of the following is true? *
| | There exist x, y belonging to L(G) such that xy does not belong to L(G). |
| | There is a DPDA that accepts L(G). |
| | We can find a DFA that accepts L(G). |
If M is a NDPDA accepting L, then which of the following is true: *
| | There always exist a DPDA equivalent to M accepting L. |
| | There does not exist a DPDA equivalent to M accepting L. |
| | There may exist a DPDA equivalent to M accepting L. |
If a Context free grammar G, is in Chomsky normal form, then the length of derivation of a string w of length n, belonging to L(G) is: *
If a Context free grammar G, is in Creibach normal form, then the length of derivation of a string w of length n, belonging to L(G) is: *
If the start symbol S of a given Context free grammar G is useless, then L(G) is: *
For an inherently ambiguous Context free language: *
| | There exists at least one Context free grammar, which is ambiguous. |
| | There exists at least one Context free grammar, which is unambiguous. |
| | There exist no Context free grammar. |
| | There exist no Context free grammar, which is unambiguous. |
Pigeon-hole principle states that if P and Q are two non-empty finite sets, then: *
| | There exist no function from P to Q. |
| | There exist no one-to-one function from P to Q. |
| | There exist no one-to-one function from Q to P. |
If L1 is a Context free language, and L2, L3 are regular languages. If L4 = L1 intersection L2 intersection L3, then L4 is: *
| | Non Context free language. |
The following Context-free grammar: S--> aB | bA ; A --> b | aS | bAA ; B --> b | bS | aBB generates strings of terminals that have *
| | Equal number of a's and b's. |
| | Odd number of a's and odd number of b's. |
| | even number of a's and even number of b's. |
| | odd number of a's and even number of a's. |
Which of the following Context-free grammar can't be simulated by a Finite-state Machine? *
| | S --> abX ; X --> cY ; Y --> d | aX |
The following transition graph *
| | Complements a given bit pattern. |
| | Finds 2's complement of a given bit pattern. |
| | Increment a given bit pattern by 1. |
The word 'formal' in formal languages mean *
| | The symbols used have well-defined language meaning. |
| | They are formal and a reality. |
| | Only the form of the string of symbols is significant. |
| | The language are unnecessary in reality. |
Which of the following is not possible algorithmically? *
| | Regular grammar to Context-free grammar. |
| | Non-deterministic finite state automata to Deterministic finite state automata. |
| | Non-deterministic PDA to Deterministic PDA. |
The vernacular language English, if considered a formal language is a *
| | Context-sensitive language. |
If there exists a Turing Machine which when applied to any problem in the class, terminates, if the correct answer is yes and may or may not terminate otherwise is said to be *
Universal Turing Machine influenced the concept of *
| | Stored program computers. |
| | Interpretive implementation of programming language. |
Which of the following is accepted by an Non-deterministic PDA but not by a Deterministic PDA? *
| | All strings in which a given symbol is present at least twice. |
| | Strings ending with a particular alphabet. |
Turing Machine is more powerful than Finite-state machines because *
| | Tape movement in a Finite-state machine is confined to one direction only. |
| | TM has no finite state control. |
| | TM has the capability to remember arbitary long sequence of input symbols. |
Regarding the power of recognition of languages, which of the following statement is false? *
| | The NFA is equivalent to DFA. |
| | The Non-deterministic PDA is equivalent to Deterministic PDA. |
| | The Non-deterministic TM is equivalent to Deterministic TM. |
| | Multi-tape TM are equivalent to standard TM. |
The language constructs which are most useful in describing nested structures such as balanced parenthesis is *
| | Context-sensitive grammar |
Which of the following statement is true? *
| | All languages can be generated by Context-free grammar. |
| | The number of symbols necessary to simulate a TM with m symbols and n states is mn. |
| | Any regular grammar has an equivalent Context-free grammar. |
| | The classes of Context-free language is not closed under union. |
The production for certain grammar { S--> aSbb | abb } is *
Define for a Context-free language L, init(L) = { u | uv belongs to L for some v in {0,1}* }. In other words init(L) is the set of prefixes of L. Let L = { w | w in {0,1}{0,1}*, w has equal number of 0's and 1's }. Then init (L) is *
| | the set of all binary strings with unequal number of 0's and 1's. |
| | the set of all binary strings including null string. |
| | the set of all binary strings with exactly one more 0 than the number of 1's. |
For the grammar : S--> AC | CB ; C --> aCb | a | b ; A -->aA | lemda ; B --> Bb | lemda what is the minimum length of the derivation (starting from S) to generate the string with all a's first followed by b's and the number of a's and b's are not equal. *
| | maximum ( number of a's, number of b's ) + 2 |
| | number of a's + number of b's + 2 |
| | number of a's + number of b's + 3 |
| | maximum ( number of a's, number of b's ) + 3 |
Let NF and NP denote the classes of languages accepted by nondeterministic Finite acceptor and nondeterministic Push down acceptor respectively. Let DF and DP denote the classes of languages accepted by deterministic Finite acceptor and deterministic Push down acceptor respectively. Which of the following is TRUE? *
| | DF is a subset of NF and DP is a subset of NP. |
| | DF is a subset of NF and DP equals NP. |
| | DF equals NF and DP is a subset of NP. |
| | DF equals NF and DP equals NP. |
0 Comments