Question 1

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 0's.
C)The set of all strings containing at least two 0's.
D)The set of all strings that begin and end with either 0 or 1.

Accepted Answer

The regular expression (0+1)*0(0+1)*0(0+1)* describes the set of all strings that can have any combination of 0s and 1s but must contain at least two 0s at any position. The parts (0+1)* allow for any sequence of 0s and 1s (including none), and the 0(0+1)*0 ensures there are at least two 0s in the string.

Question 2

Which one of the following is FALSE?
A)There is 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.

Accepted Answer

Deterministic and nondeterministic PDAs are not equivalent in power. While every nondeterministic PDA can be converted into an equivalent context-free grammar, there is no general method to convert every nondeterministic PDA into an equivalent deterministic PDA, as deterministic PDAs are strictly less powerful than nondeterministic ones.

Question 3

Match all items in Group 1 with correct options from those given in Group 2.
List I &emsp;List II
p. Regular Expression &emsp; 1. Syntax analysis
q. Push down automata &emsp; 2. Code Generation
r. Dataflow analysis &emsp; 3. Lexical analysis
s. Register allocation &emsp; 4. Code optimization
A)P-4. Q-1, R-2, S-3
B)P-3, Q-1, R-4, S-2
C)P-3, Q-4, R-1, S-2
D)P-2, Q-1, R-4, S-3

Accepted Answer

- Regular Expression is used in Lexical analysis to define patterns for tokens, hence P-3.- Push down automata are used in Syntax analysis as they can handle context-free languages, hence Q-1.- Dataflow analysis is a technique used in Code optimization to improve the performance of code by analyzing the flow of data, hence R-4.- Register allocation is part of Code Generation where variables are assigned to machine registers, hence S-2.

Question 4

Which of the following pairs have DIFFERENT expressive power?
A)Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B)Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C)Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D)Single-tape Turing machine and multi-tape Turing machine

Accepted Answer

Deterministic push down automata (DPDA) and Non-deterministic pushdown automata (NPDA) have different expressive powers because NPDAs can recognize some context-free languages that DPDAs cannot, such as the classic example of the language {a^n b^n c^n | n ≥ 0}.

Question 5

Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
A)ScT (S is a subset of T)
B)TcS (T is a subset of S)
C)S=T
D)SnT=Ø

Accepted Answer

The answer of Let S and T be language over...

Question 6

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?
A)L = O
B)L is regular but not O
C)L is context free but not regular
D)L is not context free

Accepted Answer

The answer of Let L denotes the language generated by...

Question 7

Consider the following two statements: S₁: { 0^2n |n >= l} is a regu1ar language S₂: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language Which of the following statements is correct? A)Only S₁ is correct B)Only S₂ is correct C)Both S₁ and S₂ are correct D)None of S₁ and S₂ is correct

Accepted Answer

The answer of Consider the following two statements: S₁: { 0^2n...

Question 8

Which of the following statements in true?
A)If a language is context free it can always be accepted by a deterministic push-down automaton
B)The union of two context free languages is context free
C)The intersection of two context free languages is context free
D)The complement of a context free language is context free

Accepted Answer

The union of two context-free languages is context-free because context-free languages are closed under union. This means that if you have two languages that can each be described by a context-free grammar, you can construct a new context-free grammar that describes the language consisting of all strings that are in either of the original languages.

Question 9

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.
A)N^2
B)2^N
C)2N
D)N!

Accepted Answer

The maximum number of states in an equivalent minimized DFA for a given NFA with N states is 2^N. This is because, in the worst-case scenario, each state in the DFA could represent a unique combination of NFA states, leading to a total of 2^N possible states.

Question 10

Which of the following is true for the language {a^p} p is prine ?
A)It is not accepted by a turing machine
B)It is regular but not context free
C)It is context free but not regular
D)It is neither regular nor context free but accepted by a turing machine

Accepted Answer

The language {a^p | p is prime} is not regular because it does not satisfy the pumping lemma for regular languages. It is also not context-free, as context-free languages cannot handle the prime number constraint without additional mechanisms. However, it can be accepted by a Turing machine, which is capable of performing the necessary computations to check if the length of the string (number of 'a's) is prime. Turing machines are more powerful than both finite automata and pushdown automata, which recognize regular and context-free languages, respectively.

Question 11

Which of the following are decidable ?
1) whether the intersection of two regular language is infinite.
2) whether a give context free language is regular
3) whether two push down automata accept the same language.
4) whether a given grammar is context free
A)1 and 2
B)1 and 4
C)2 and 3
D)2 and 4

Accepted Answer

1) The intersection of two regular languages is decidable because regular languages are closed under intersection, and it is possible to construct a finite automaton for the intersection and then check if this automaton accepts an infinite number of strings (e.g., by checking for cycles in its state graph).4) Determining whether a given grammar is context-free is decidable because the definition of a context-free grammar is based on specific rules (productions of the form $A \rightarrow \alpha$, where $A$ is a single non-terminal and $\alpha$ is a string of terminals and/or non-terminals), which can be checked algorithmically.

Question 12

If L and L' are recursively enumerable, then L is
A)regular
B)context free
C)context sensitive
D)recursive

Accepted Answer

The property of being recursively enumerable does not imply that a language is regular, context-free, or context-sensitive. However, if a language L is recursively enumerable and its complement L' is also recursively enumerable, then L is recursive. This is because a language is recursive if and only if both the language and its complement are recursively enumerable.

Question 13

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules
S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA
Which of the following strings is generated by the grammar?
A)aaaabb
B)aabbbb
C)aabbab
D)abbbba

Accepted Answer

The answer of Consider the CFG with {S,A,B) as the...

Question 14

Consider the following context free languages: L₁ = {0^i 1^j 2^k | i+j = k} L₂ = {0^i 1^j 2^k | i = j or j = k} L₃ = {0^i 1^j | i = 2j+1} Which of the following option is true? A)L₁, L₂ and L₃ can be recognized by Deterministic Push down automata B)L₁, L₂ can be recognized by Deterministic Push down automata C)L₁, L₃ can be recognized by Deterministic Push down automata D)None of the above

Accepted Answer

L₁ and L₃ can be recognized by deterministic pushdown automata (DPDA) because they have a specific pattern that allows a DPDA to track the relationship between the numbers of 0s, 1s, and 2s (for L₁) and between the numbers of 0s and 1s (for L₃) deterministically. L₂, however, involves a non-deterministic choice (i = j or j = k) which cannot be resolved by a DPDA.

Question 15

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
A)I and II
B)I and IV
C)II and III
D)II and IV

Accepted Answer

I. The intersection of two regular languages is also regular, and it is decidable whether a regular language is infinite.IV. It is decidable whether a given grammar is context-free because the form of the rules in the grammar can be checked against the definition of a context-free grammar.

Question 16

Let be the encoding of a Turing machine as a string over ?= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is A)decidable and recursively enumerable B)undecidable but recursively enumerable C)undecidable and not recursively enumerable D)decidable but not recursively enumerable

Accepted Answer

L is undecidable because determining whether a Turing machine accepts a string of a specific length (in this case, 2014) is equivalent to solving the Halting Problem, which is known to be undecidable. However, L is recursively enumerable because we can enumerate all strings of length 2014 and simulate the Turing machine on each string to see if it accepts any of them. If it does, we can list the encoding of that Turing machine. This process does not halt for machines that do not accept any string of length 2014, which is why L is not decidable but is recursively enumerable.

Question 17

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE? A)P3 is decidable if P₁ is reducible to P₃ B)P3 is undecidable if P₃ is reducible to P₂ C)P3 is undecidable if P₂ is reducible to P₃ D)P3 is decidable if P₃ is reducible to P₂'s complement

Accepted Answer

The answer of Consider three decision problems P₁, P₂ and...

Question 18

Consider the following decision problems: (P₁) Does a given finite state machine accept a given string (P₂) Does a given context free grammar generate an infinite number of stings Which of the following statements is true? A)Both (P₁) and (P₂) are decidable B)Neither (P₁) nor (P₂) are decidable C)Only (P₁) is decidable D)Only (P₂) is decidable

Accepted Answer

(P₁) is decidable because we can simulate the finite state machine on the given string to determine acceptance. (P₂) is also decidable because there are algorithms to determine if a context-free grammar generates an infinite number of strings by checking for recursive production rules.

Question 19

Which of the following statements is false?
A)Every context-sensitive language is recursive.
B)The set of all languages that are not recursively enumerable is countable.
C)The family of recursively enumerable languages is closed under union.
D)The families of recursively enumerable and recursive languages are closed under reversal

Accepted Answer

The set of all languages that are not recursively enumerable is uncountable. This is because the set of all possible languages over a finite alphabet is uncountable, and the set of recursively enumerable languages is countable, leaving an uncountable number of languages that are not recursively enumerable.

Question 20

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
A)(L + D) *
B)(L.D) *
C)L(L + D) *
D)L(L.D) *

Accepted Answer

Option C, L(L + D)*, correctly defines an identifier that starts with a letter followed by any number of letters or digits. The first L ensures the identifier starts with a letter, and (L + D)* allows for any combination of letters and digits thereafter, including none.

Quiz 2: Formal Languages and Automata Theory: Part B

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) *?

Which one of the following is FALSE?

Match all items in Group 1 with correct options from those given in Group 2. List I List II p. Regular Expression 1. Syntax analysis q. Push down automata 2. Code Generation r. Dataflow analysis 3. Lexical analysis s. Register allocation 4. Code optimization

Which of the following pairs have DIFFERENT expressive power?

Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b) *, respectively. Which of the following is true?

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?

Consider the following two statements: S₁: { 0^2n |n >= l} is a regu1ar language S₂: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language Which of the following statements is correct?

Which of the following statements in true?

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

Which of the following is true for the language {a^p} p is prine ?

Which of the following are decidable ? 1) whether the intersection of two regular language is infinite. 2) whether a give context free language is regular 3) whether two push down automata accept the same language. 4) whether a given grammar is context free

If L and L' are recursively enumerable, then L is

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules S --> aB S --> bA B --> b A --> a B --> bS A --> aS B --> aBB A --> bAA Which of the following strings is generated by the grammar?

Consider the following context free languages: L₁ = {0^i 1^j 2^k | i+j = k} L₂ = {0^i 1^j 2^k | i = j or j = k} L₃ = {0^i 1^j | i = 2j+1} Which of the following option is true?

Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free

Let be the encoding of a Turing machine as a string over ?= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

Consider the following decision problems: (P₁) Does a given finite state machine accept a given string (P₂) Does a given context free grammar generate an infinite number of stings Which of the following statements is true?

Which of the following statements is false?

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?