Formal Language & Automata Theory
-
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?
-
ScT (S is a subset of T)
-
TcS (T is a subset of S)
-
S=T
-
SnT=Ø
-
This quiz on Formal Language & Automata Theory covers key topics such as regular languages, context-free languages, and finite automata. It assesses understanding of language See moreequality, language properties, and automaton state minimization. Essential for students in computer science, especially those focusing on theoretical aspects.
- 2.
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
-
L = O
-
L is regular but not O
-
L is context free but not regular
-
L is not context free
Correct Answer
A. L is regular but not OExplanation
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.Rate this question:
-
- 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?
-
Only S1 is correct
-
Only S2 is correct
-
Both S1 and S2 are correct
-
None of S1 and S2 is correct
Correct Answer
A. Both S1 and S2 are correctExplanation
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.Rate this question:
-
- 4.
Which of the following statements in true?
-
If a language is context free it can always be accepted by a deterministic push-down automaton
-
The union of two context free languages is context free
-
The intersection of two context free languages is context free
-
The complement of a context free language is context free
Correct Answer
A. The union of two context free languages is context freeExplanation
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.Rate this question:
-
- 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.
-
N^2
-
2^N
-
2N
-
N!
Correct Answer
A. 2^NExplanation
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.Rate this question:
-
- 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?
-
(0*10*1)*
-
0*(10*10*)*
-
0*(10*1*)*0*
-
0*1(10*1)*10*
Correct Answer
A. 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.Rate this question:
-
- 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?
-
L2 – L1 is recursively enumerable.
-
L1 – L3 is recursively enumberable
-
L2 \cap L1 is recursively enumberable
-
L2 \cup L1 is recursively enumberable
Correct Answer
A. L1 – L3 is recursively enumberableExplanation
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.Rate this question:
-
- 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?
-
Only L2 is context free
-
Only L2 and L3 are context free
-
Only L1 and L2 are context free
-
All are context free
Correct Answer
A. All are context freeExplanation
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.Rate this question:
-
- 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?
-
n-1
-
N
-
N+1
-
2n-1
Correct Answer
A. n-1Explanation
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.Rate this question:
-
- 10.
Given the language L = {ab, aa, baa}, whih of the following strings are in L*?….1) abaabaaabaa….2) aaaabaaaa….3) baaaaabaaaab….4) baaaaabaa
-
1, 2 and 3
-
2, 3 and 4
-
1, 2 and 4
-
1, 3 and 4
Correct Answer
A. 1, 2 and 4Explanation
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.Rate this question:
-
- 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?
-
1, 2, 3, 4
-
1, 2
-
2, 3, 4
-
3, 4
Correct Answer
A. 3, 4Explanation
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.Rate this question:
-
- 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 {pnqn|n N}). Then which of the following is ALWAYS regular?
-
P Q
![Formal Language & Automata Theory - Quiz]()
-
P – Q
-
* – P
![Formal Language & Automata Theory - Quiz]()
-
* – Q
![Formal Language & Automata Theory - Quiz]()
Correct Answer
A. * – PExplanation
The expression "* - P" is always regular because when we subtract a regular language from any language, the resulting language is always regular.Rate this question:
-
- 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?
-
Push Down Automata (PDA) can be used to recognize L1 and L2
-
L1 is a regular language
-
All the three languages are context free
-
Turing machine can be used to recognize all the three languages
Correct Answer
A. All the three languages are context freeExplanation
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.Rate this question:
-
- 14.
S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
-
All palindromes.
-
All odd length palindromes.
-
Strings that begin and end with the same symbol
-
All even length palindromes.
Correct Answer
A. 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."Rate this question:
-
- 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)*?
-
The set of all strings containing the substring 00.
-
The set of all strings containing at most two 0’s.
-
The set of all strings containing at least two 0’s.
-
The set of all strings that begin and end with either 0 or 1.
Correct Answer
A. 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.Rate this question:
-
- 16.
Which one of the following is FALSE?
-
There is unique minimal DFA for every regular language
-
Every NFA can be converted to an equivalent PDA.
-
Complement of every context-free language is recursive.
-
Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Correct Answer
A. 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
-
P-4. Q-1, R-2, S-3
-
P-3, Q-1, R-4, S-2
-
P-3, Q-4, R-1, S-2
-
P-2, Q-1, R-4, S-3
Correct Answer
A. P-3, Q-1, R-4, S-2Explanation
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.Rate this question:
-
- 18.
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
-
7
-
10
-
12
-
11
Correct Answer
A. 11Explanation
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.Rate this question:
-
- 19.
Which of the following is true?
-
(01)*0 = 0(10)*
-
(0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
-
(0+1)*01(0+1)*+1*0* = (0+1)*
-
All of the mentioned
Correct Answer
A. All of the mentionedExplanation
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.Rate this question:
-
- 20.
A language is regular if and only if
-
Accepted by DFA
-
Accepted by PDA
-
accepted by LBA
-
Accepted by Turing machine
Correct Answer
A. Accepted by DFAExplanation
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.Rate this question:
-
- 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
-
L1
-
L1>=L2
-
L1 U L2 = .*
-
L1=L2
Correct Answer
A. L1=L2Explanation
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.Rate this question:
-
- 22.
Which of the following is not a regular expression?
-
[(a+b)*-(aa+bb)]*
-
[(0+1)-(0b+a1)*(a+b)]*
-
(01+11+10)*
-
(1+2+0)*(1+2)*
Correct Answer
A. [(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.Rate this question:
-
- 23.
Regular expression are
-
Type 0 language
-
Type 1 language
-
Type 2 language
-
Type 3 language
Correct Answer
A. Type 0 languageExplanation
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.Rate this question:
-
- 24.
Which of the following is true?
-
Every subset of a regular set is regular
-
Every finite subset of non-regular set is regular
-
The union of two non regular set is not regular
-
Infinite union of finite set is regular
Correct Answer
A. Every finite subset of non-regular set is regularExplanation
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.Rate this question:
-
- 25.
L and ~L are recursive enumerable then L is
-
Regular
-
Context free
-
Context sensitive
-
Recursive
Correct Answer
A. RecursiveExplanation
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.Rate this question:
-
- 26.
Regular expressions are closed under
-
Union
-
Intersection
-
Kleen star
-
All of the mentioned
Correct Answer
A. All of the mentionedExplanation
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.Rate this question:
-
- 27.
Regular expression {0,1} is equivalent to
-
0 U 1
-
0 / 1
-
0 + 1
-
All of above
Correct Answer
A. All of aboveExplanation
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}.Rate this question:
-
- 28.
A regular language over an alphabet a is one that can be obtained from
-
Union
-
Concatenation
-
Kleene
-
All of above
Correct Answer
A. All of aboveExplanation
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".Rate this question:
-
- 29.
Precedence of regular expression in decreasing order is
-
* , . , +
-
. , * , +
-
. , + , *
-
+ , a , *
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.Rate this question:
-
- 30.
Regular expression Φ* is equivalent to
-
ϵ
-
Φ
-
0
-
1
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 ϵ.Rate this question:
-
- 31.
a? is equivalent to
-
A
-
A+Φ
-
A+ϵ
-
wrong expression
Correct Answer
A. 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.Rate this question:
-
- 32.
ϵL is equivalent to
-
ϵ
-
Φ
-
L
-
Lϵ
Correct Answer
A. 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.Rate this question:
-
- 33.
(a+b)* is equivalent to
-
b*a*
-
(a*b*)*
-
A*b*
-
none of above
Correct Answer
A. (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.Rate this question:
-
- 34.
ΦL is equivalent to
-
LΦ
-
Φ
-
Φ
-
ϵ
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.Rate this question:
-
- 35.
Which of the following pair of regular expression are not equivalent?
-
1(01)* and (10)*1
-
X(xx)* and (xx)*x
-
(ab)* and a*b*
-
X+ and x*x+
Correct Answer
A. (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.Rate this question:
-
- 36.
Consider following regular expressioni) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)*Which of the following statements is correct
-
I,ii are equal and ii,iii are not
-
I,ii are equal and i,iii are not
-
Ii,iii are equal and i,ii are not
-
All are equal
Correct Answer
A. All are equalExplanation
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.Rate this question:
-
- 37.
Number of states require to accept string ends with 10.
-
3
-
2
-
1
-
Can’t be represented.
Correct Answer
A. 3Explanation
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.Rate this question:
-
- 38.
Language of finite automata is.
-
Type 0
-
Type 1
-
Type 2
-
Type 3
Correct Answer
A. Type 3Explanation
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.Rate this question:
-
- 39.
Finite automata requires minimum _______ number of stacks.
-
1
-
0
-
2
-
None of the mentioned
Correct Answer
A. 0Explanation
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.Rate this question:
-
- 40.
Regular expression for all strings starts with ab and ends with bba is.
-
aba*b*bba
-
Ab(ab)*bba
-
Ab(a+b)*bba
-
All of the mentioned
Correct Answer
A. Ab(a+b)*bbaExplanation
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.Rate this question:
-
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 21, 2023Quiz Edited by
ProProfs Editorial Team -
Mar 25, 2015Quiz Created by
Rabib
Back to top