1.
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?
Correct Answer
C. S=T
Explanation
The regular expression (a+b*)* represents a language that consists of any combination of 'a' and 'b', including an empty string. The regular expression (a+b)* represents a language that consists of any combination of 'a' and 'b', but does not include an empty string. Therefore, the language represented by (a+b*)* is a superset of the language represented by (a+b)*. Since S is a superset of T, it can be concluded that S=T.
2.
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
Correct Answer
B. L is regular but not O
Explanation
The given grammar S → OSO/00 generates a language denoted by L. This language L consists of strings that can be formed by either concatenating an O with another string from L and then concatenating it with an O, or by directly appending 00 to the end of a string in L. This means that L contains strings of the form O^n00, where n is a non-negative integer. Since L can be generated by a regular grammar, it is regular. On the other hand, the language O consists of strings of the form O^n, where n is a non-negative integer. O is not regular because it cannot be generated by a regular grammar. Therefore, the statement "L is regular but not O" is true.
3.
Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?
Correct Answer
C. Both S1 and S2 are correct
Explanation
Both S1 and S2 are correct.
S1 represents the language of strings consisting of a sequence of 0's raised to an even power, where n is greater than or equal to 1. This language can be represented by a regular expression (0^2)*, where 0^2 represents a sequence of two 0's. Therefore, S1 is a regular language.
S2 represents the language of strings consisting of a sequence of 0's raised to the power of m, followed by a sequence of 0's raised to the power of n, followed by a sequence of 0's raised to the power of m+n, where m is greater than or equal to 1 and n is greater than or equal to 2. This language can also be represented by a regular expression (0^m)(0^n)(0^(m+n)), where (0^m) represents a sequence of m 0's. Therefore, S2 is also a regular language.
4.
Which of the following statements in true?
Correct Answer
B. The union of two context free languages is context free
Explanation
The correct answer is "The union of two context free languages is context free". This statement is true because the union of two context free languages can be recognized by a context free grammar. The grammar can be constructed by taking the union of the production rules of the two individual context free grammars. Thus, any string that belongs to either of the two languages can be generated by the resulting grammar, making the union context free.
5.
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.
Correct Answer
B. 2^N
Explanation
The correct answer is 2^N. In an NFA, each state can have multiple possible transitions for a given input symbol or even for epsilon transitions. In a DFA, each state can only have one transition for a given input symbol. Therefore, to convert an NFA with N states into an equivalent minimized DFA, we need to consider all possible combinations of states in the NFA, which results in 2^N states in the DFA.
6.
Let L={w (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
Correct Answer
B. 0*(10*10*)*
Explanation
The regular expression "0*(10*10*)*" represents the language L, which is the set of all bit strings with an even number of 1s. This regular expression can be broken down as follows:
- "0*" matches any number of 0s, including zero occurrences.
- "(10*10*)*" matches any number of occurrences of the pattern "10*10*", which consists of a 1 followed by any number of 0s, followed by another 1, followed by any number of 0s. This pattern ensures that there is an even number of 1s in the string.
Therefore, the regular expression correctly represents the language L.
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?
Correct Answer
B. L1 – L3 is recursively enumberable
Explanation
The statement "L1 – L3 is recursively enumerable" is not necessarily true. This is because the difference between a recursively enumerable language and a recursive language may not always be recursively enumerable. In other words, it is possible for L1 – L3 to be a language that is not recursively enumerable.
8.
Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i = 2j+1}, L4 = {|i != 2j}. Which one of the following statements is true?
Correct Answer
D. All are context free
Explanation
The given answer is correct because all the languages L1, L2, L3, and L4 can be generated by context-free grammars. L1 can be generated by a context-free grammar that has a production rule for every pair of non-equal terminals. L2 can be generated by a context-free grammar that has a production rule for every pair of equal terminals. L3 can be generated by a context-free grammar that has a production rule for every odd number. L4 can be generated by a context-free grammar that has a production rule for every non-equal pair of integers where the second integer is twice the first integer.
9.
Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
Correct Answer
A. n-1
Explanation
The minimum number of states in a non-deterministic finite automaton that accepts L, where L is the set of all substrings of a string w of length n, is n-1. This is because each state in the automaton represents a prefix of w, and there are n possible prefixes of length 1 to n. However, the empty string is not included in L, so we subtract 1 from the total number of prefixes to get n-1 states.
10.
Given the language L = {ab, aa, baa}, whih of the following strings are in L*?….1) abaabaaabaa….2) aaaabaaaa….3) baaaaabaaaab….4) baaaaabaa
Correct Answer
C. 1, 2 and 4
Explanation
The language L* represents the set of all possible combinations of strings from L, including the empty string.
In this case, L = {ab, aa, baa}.
1) The string "abaabaaabaa" can be obtained by concatenating the strings "ab", "aa", and "baa" from L. Therefore, it is in L*.
2) The string "aaaabaaaa" can be obtained by concatenating the string "aa" from L multiple times. Therefore, it is in L*.
3) The string "baaaaabaaaab" cannot be obtained by concatenating any strings from L. Therefore, it is not in L*.
4) The string "baaaaabaa" can be obtained by concatenating the strings "baa" and "aa" from L. Therefore, it is in L*.
Thus, the correct answer is 1, 2, and 4.
11.
Which of the following problems are decidable?….1) Does a given program ever produce an output?….2) If L is a context-free language, then is L’ (complement of L) also context-free?….3) If L is a regular language, then is L’ also regular?….4) If L is a recursive language, then, is L’ also recursive?
Correct Answer
D. 3, 4
Explanation
The given correct answer is 3, 4. This means that problems 3 and 4 are decidable. Problem 3 asks if the complement of a regular language is also regular, and problem 4 asks if the complement of a recursive language is also recursive. Both of these problems can be solved algorithmically, making them decidable.
12.
Let P be a regular language and Q be context-free language such that Q P. (For example, let P be the language represented by the regular expression p*q* and Q be {p^{n}q^{n}|n N}). Then which of the following is ALWAYS regular?
Correct Answer
C. * – P
Explanation
The expression "* - P" is always regular because when we subtract a regular language from any language, the resulting language is always regular.
13.
Consider the language L1,L2,L3 as given below.L1={ | p,q N}L2={ | p,q N and p=q}L3={ | p,q,r N and p=q=r}Which of the following statements is NOT TRUE?
Correct Answer
C. All the three languages are context free
Explanation
The given answer is correct because all three languages, L1, L2, and L3, can be recognized by push-down automata (PDA), which are a type of non-deterministic finite automata with a stack. L1 and L2 can be recognized by a PDA because they can be defined by regular expressions, while L3 can be recognized by a PDA with multiple stacks. However, none of the languages are regular, as L1 and L2 have a condition that p must be equal to q, and L3 has a condition that p must be equal to q and r. Therefore, the statement that L1 is a regular language is not true.
14.
S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
Correct Answer
B. All odd length palindromes.
Explanation
The given grammar generates strings that are palindromes, as it has productions that allow for the repetition of the same symbol on both sides of the middle symbol. However, it only generates palindromes with odd lengths because the production aSa and bSb require the middle symbol to be the same as the symbols on the ends. Therefore, the correct answer is "All odd length palindromes."
15.
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)*?
Correct Answer
C. The set of all strings containing at least two 0’s.
Explanation
The regular expression (0+1)*0(0+1)*0(0+1)* matches any string that contains at least two 0's. The expression (0+1)* allows for any combination of 0's and 1's, including no 0's at all. The first and second instances of 0 ensure that there are at least two 0's in the string. The final (0+1)* allows for any combination of 0's and 1's after the second 0. Therefore, the correct answer is the set of all strings containing at least two 0's.
16.
Which one of the following is FALSE?
Correct Answer
D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
17.
Match all items in Group 1 with correct options from those given in Group 2.Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
Correct Answer
B. P-3, Q-1, R-4, S-2
Explanation
The correct answer is P-3, Q-1, R-4, S-2. This is because regular expressions are used in lexical analysis, pushdown automata are used in syntax analysis, dataflow analysis is used in code optimization, and register allocation is used in code generation.
18.
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
Correct Answer
D. 11
Explanation
The regular expression (x+y)*y(a+ab)* describes a language where any string can start with any number of x's or y's, followed by a y, and then followed by any number of a's or ab's. To find the number of strings of length less than 4 that contain this language, we can analyze the possible combinations. The strings can be: y, ya, yab, yy, yya, yyab, yyy. Therefore, there are 7 strings of length less than 4 that contain the described language.
19.
Which of the following is true?
Correct Answer
D. All of the mentioned
Explanation
All of the mentioned options are true. The equation (01)*0 = 0(10)* is true because any number of 0s followed by a 1, followed by any number of 0s is equal to any number of 0s. The equation (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)* is true because any number of 0s or 1s followed by a 0, followed by any number of 0s or 1s, followed by a 1, followed by any number of 0s or 1s is equal to any number of 0s or 1s followed by 01 followed by any number of 0s or 1s. The equation (0+1)*01(0+1)*+1*0* = (0+1)* is true because any number of 0s or 1s followed by 01 followed by any number of 0s or 1s, followed by any number of 1s, followed by any number of 0s is equal to any number of 0s or 1s. Therefore, all of the mentioned options are true.
20.
A language is regular if and only if
Correct Answer
A. Accepted by DFA
Explanation
A language is considered regular if and only if it can be accepted by a Deterministic Finite Automaton (DFA). A DFA is a type of automaton that recognizes regular languages, which are languages that can be described by regular expressions. Regular languages are characterized by their ability to be recognized and accepted by a DFA, making this the correct answer.
21.
Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
Correct Answer
D. L1=L2
Explanation
The answer "L1=L2" suggests that the class of languages accepted by a finite state machine (L1) is equal to the class of languages represented by regular expressions (L2). This means that any language that can be accepted by a finite state machine can also be represented by a regular expression, and vice versa. It implies that the two classes are equivalent in terms of their expressive power and can be used interchangeably to describe the same set of languages.
22.
Which of the following is not a regular expression?
Correct Answer
B. [(0+1)-(0b+a1)*(a+b)]*
Explanation
The given regular expression [(0+1)-(0b+a1)*(a+b)]* is not a regular expression because it contains the subtraction operation (-) which is not a valid operation in regular expressions. Regular expressions only allow for operations such as concatenation, union, and Kleene star.
23.
Regular expression are
Correct Answer
A. Type 0 language
Explanation
Regular expressions are a way to describe patterns in strings. They are a powerful tool for searching, matching, and manipulating text. Type 0 languages, also known as unrestricted grammars, are the most powerful type of formal language in the Chomsky hierarchy. They can describe any language that can be recognized by a Turing machine, making them more expressive than Type 1, Type 2, and Type 3 languages. Therefore, regular expressions are considered Type 0 languages.
24.
Which of the following is true?
Correct Answer
B. Every finite subset of non-regular set is regular
Explanation
Every finite subset of a non-regular set is regular because a non-regular set is a set that cannot be described by a regular expression or recognized by a finite automaton. However, a finite subset of a non-regular set can be described by a regular expression or recognized by a finite automaton, making it regular.
25.
L and ~L are recursive enumerable then L is
Correct Answer
D. Recursive
Explanation
If L and ~L are recursively enumerable, it means that there exist Turing machines that can enumerate all the strings in L and ~L. This implies that L is recursively enumerable. Recursive enumerable languages are a superset of regular, context-free, and context-sensitive languages. Therefore, L can be any of these types, but it is definitely recursive.
26.
Regular expressions are closed under
Correct Answer
D. All of the mentioned
Explanation
Regular expressions are closed under all of the mentioned operations, which means that applying any of these operations to regular expressions will always result in a regular expression. The union of two regular expressions will produce a regular expression that matches either of the original expressions. The intersection of two regular expressions will produce a regular expression that matches only the strings that are matched by both original expressions. The Kleene star operation applied to a regular expression will produce a regular expression that matches zero or more occurrences of the original expression. Therefore, all of these operations preserve the regularity of regular expressions.
27.
Regular expression {0,1} is equivalent to
Correct Answer
D. All of above
Explanation
The regular expression {0,1} represents a choice between 0 and 1. The notation "0 U 1" denotes the union of 0 and 1, meaning either 0 or 1 can be matched. The notation "0 / 1" denotes the division of 0 by 1, which is not a valid regular expression operation. The notation "0 + 1" denotes the addition of 0 and 1, which is also not a valid regular expression operation. Therefore, the correct answer is "All of above" because all the given options are equivalent to the regular expression {0,1}.
28.
A regular language over an alphabet a is one that can be obtained from
Correct Answer
D. All of above
Explanation
A regular language over an alphabet 'a' can be obtained from the union of two or more regular languages, the concatenation of regular languages, and the Kleene closure of a regular language. Therefore, the correct answer is "All of above".
29.
Precedence of regular expression in decreasing order is
Correct Answer
A. * , . , +
Explanation
The given answer is the correct order of precedence for the given regular expressions. The asterisk (*) has the highest precedence, followed by the dot (.), and then the plus (+) symbol. This means that any expression enclosed in parentheses with an asterisk will be evaluated first, followed by any expression with a dot, and finally any expression with a plus symbol.
30.
Regular expression Φ* is equivalent to
Correct Answer
A. ϵ
Explanation
The regular expression ϕ* represents the language that contains zero or more occurrences of the empty string. The empty string, denoted by ϵ, is a string with no characters. So, the correct answer is ϵ.
31.
a? is equivalent to
Correct Answer
C. A+ϵ
Explanation
The correct answer is a+ϵ. In mathematical notation, ϵ represents a small positive value that is arbitrarily close to zero. Therefore, adding ϵ to a is equivalent to adding a very small positive value to a.
32.
ϵL is equivalent to
Correct Answer
D. Lϵ
Explanation
The correct answer is Lϵ because the symbol ϵ represents the empty string or the absence of any characters. Therefore, when L is concatenated with the empty string, the resulting language would still be L.
33.
(a+b)* is equivalent to
Correct Answer
B. (a*b*)*
Explanation
The correct answer is (a*b*)* because it represents a regular expression that matches any string that consists of zero or more occurrences of the pattern "a*b*", where "a" can occur zero or more times followed by "b" occurring zero or more times. This regular expression can match strings such as "", "b", "a", "ab", "aab", "abb", "aaab", "aabb", etc. Therefore, (a*b*)* is the correct equivalent expression.
34.
ΦL is equivalent to
Correct Answer
A. LΦ
Explanation
The correct answer is LΦ because Φ is the empty string, which means it has no characters. When we concatenate Φ with any string L, the result is still L. Therefore, LΦ is equivalent to L.
35.
Which of the following pair of regular expression are not equivalent?
Correct Answer
C. (ab)* and a*b*
Explanation
The regular expressions (ab)* and a*b* are not equivalent because the first expression matches any number of occurrences of the string "ab" consecutively, while the second expression matches any number of occurrences of either "a" or "b" in any order. Therefore, the first expression will not match strings like "aaabbb" or "ababab", whereas the second expression will.
36.
Consider following regular expressioni) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)*Which of the following statements is correct
Correct Answer
D. All are equal
Explanation
The correct answer is "all are equal." This means that all three regular expressions (i), (ii), and (iii) are equivalent to each other. This can be determined by analyzing the patterns and rules of each regular expression. In this case, all three expressions allow for any combination of 'a' and 'b' characters, including an empty string (represented by ϵ). Therefore, they describe the same language and are considered equal.
37.
Number of states require to accept string ends with 10.
Correct Answer
A. 3
Explanation
To accept a string that ends with "10", we need to consider all possible combinations of states that can lead to this ending. The first state represents the initial state, the second state represents the state after reading the first character, and the third state represents the state after reading the second character. By having three states, we can ensure that the string ends with "10" by transitioning from the first state to the second state after reading any character, and then transitioning from the second state to the third state only when the second character is "0". Therefore, the correct answer is 3.
38.
Language of finite automata is.
Correct Answer
D. Type 3
Explanation
The language of finite automata is Type 3. Type 3 languages are also known as regular languages, which can be recognized and generated by finite automata. These languages can be described by regular expressions and can be accepted by deterministic or non-deterministic finite automata. Type 3 languages are the simplest type of languages in the Chomsky hierarchy, and they include regular expressions, regular grammars, and regular sets.
39.
Finite automata requires minimum _______ number of stacks.
Correct Answer
B. 0
Explanation
Finite automata requires minimum 0 number of stacks because a finite automaton is a computational model that can be in one of a finite number of states at any given time. It does not require any additional memory or storage, such as a stack, to perform its computations. Therefore, the correct answer is 0.
40.
Regular expression for all strings starts with ab and ends with bba is.
Correct Answer
C. Ab(a+b)*bba
Explanation
The regular expression "ab(a+b)*bba" represents all strings that start with "ab" and end with "bba". The "ab" at the beginning ensures that the string starts with "ab", the "(a+b)*" allows for any combination of "a" or "b" in between, and the "bba" at the end ensures that the string ends with "bba". Therefore, this regular expression covers all possible strings that satisfy the given condition.