Formal Language & Automata Theory

Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Rabib
R
Rabib
Community Contributor
Quizzes Created: 3 | Total Attempts: 2,328
| Attempts: 1,401 | Questions: 40
Please wait...
Question 1 / 40
0 %
0/100
Score 0/100
1. A regular language over an alphabet a is one that can be obtained from

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

Submit
Please wait...
About This Quiz
Formal Language & Automata Theory - Quiz

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 equality, language properties, and automaton state minimization. Essential for students in computer science, especially those focusing on theoretical aspects.

Personalize your quiz and earn a certificate with your name on it!
2. Regular expressions are closed under

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.

Submit
3. A language is regular if and only if

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.

Submit
4. Regular expression {0,1} is equivalent to

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

Submit
5. 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?

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.

Submit
6. Number of states require to accept string ends with 10.

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.

Submit
7. Finite automata requires minimum _______ number of stacks.

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.

Submit
8.  Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

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.

Submit
9.  ΦL is equivalent to

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.

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

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.

Submit
11. S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of

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

Submit
12. 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
 

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.

Submit
13.  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?

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.

Submit
14.  Consider the languages L1={0^{i}1^{j}|i != j}, L2={0^{i}1^{j}|i = j}, L3 = {0^{i}1^{j}|i = 2j+1}, L4 = {0^{i}1^{j}|i != 2j}. Which one of the following statements is true?

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.

Submit
15.  Consider the language L1,L2,L3 as given below.
L1={0^{p}1^{q} | p,q \in N}L2={0^{p}1^{q} | p,q \in N and p=q}L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}Which of the following statements is NOT TRUE?

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.

Submit
16.  Which of the following is true?

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.

Submit
17. 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?

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.

Submit
18.  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)*?

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.

Submit
19. Language of finite automata is.

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.

Submit
20.  Regular expression Φ* is equivalent to

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

Submit
21. L and ~L are recursive enumerable then L is

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.

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

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.

Submit
23.  a? is equivalent to

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.

Submit
24. (a+b)* is equivalent to

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.

Submit
25. Consider following regular expression
i) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)*
Which of the following statements is correct

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.

Submit
26.  Precedence of regular expression in decreasing order is

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.

Submit
27. Which of the following pair of regular expression are not equivalent?

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.

Submit
28.  Let L={w \in (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?

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.

Submit
29. Which of the following is true?

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.

Submit
30. Which of the following statements in true?

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.

Submit
31. Which of the following is not a regular expression?

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.

Submit
32. Regular expression for all strings starts with ab and ends with bba is.

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.

Submit
33. Let P be a regular language and Q be context-free language such that Q 	\subseteq P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn|n \in N}). Then which of the following is ALWAYS regular?
 

Explanation

The expression "* - P" is always regular because when we subtract a regular language from any language, the resulting language is always regular.

Submit
34.  Which one of the following is FALSE?

Explanation

not-available-via-ai

Submit
35. Given the language L = {ab, aa, baa}, whih of the following strings are in L*?….1) abaabaaabaa….2) aaaabaaaa….3) baaaaabaaaab….4) baaaaabaa

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.

Submit
36.  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?

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.

Submit
37. ϵL is equivalent to

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.

Submit
38. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

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.

Submit
39.  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?

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.

Submit
40.  Regular expression are

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.

Submit
View My Results

Quiz Review Timeline (Updated): Mar 21, 2023 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

  • Current Version
  • Mar 21, 2023
    Quiz Edited by
    ProProfs Editorial Team
  • Mar 25, 2015
    Quiz Created by
    Rabib
Cancel
  • All
    All (40)
  • Unanswered
    Unanswered ()
  • Answered
    Answered ()
A regular language over an alphabet a is one that can be...
Regular expressions are closed under
A language is regular if and only if
Regular expression {0,1} is equivalent to
Consider the following two statements:S1: { 0^2n |n >= l} is a...
Number of states require to accept string ends with 10.
Finite automata requires minimum _______ number of stacks.
 Let the class of language accepted by finite state machine be L1...
 ΦL is equivalent to
 Given an arbitrary non-deterministic finite automaton (NFA) with...
S –> aSa| bSb| a| b ;The language generated by the above...
Match all items in Group 1 with correct options from those given in...
 Let L1 be a recursive language. Let L2 and L3 be languages that...
 Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i =...
 Consider the language L1,L2,L3 as given below.L1={ |...
 Which of the following is true?
Let S and T be language over ={a,b} represented by the regular...
 Which one of the following languages over the alphabet {0,1} is...
Language of finite automata is.
 Regular expression Φ* is equivalent to
L and ~L are recursive enumerable then L is
Let L denotes the language generated by the grammar S – OSO/00....
 a? is equivalent to
(a+b)* is equivalent to
Consider following regular expressioni) (a/b)* ii) (a*/b*)*...
 Precedence of regular expression in decreasing order...
Which of the following pair of regular expression are not...
 Let L={w  (0 + 1)*|w has even number of 1s}, i.e. L is...
Which of the following is true?
Which of the following statements in true?
Which of the following is not a regular expression?
Regular expression for all strings starts with ab and ends with bba...
Let P be a regular language and Q be context-free language such that...
 Which one of the following is FALSE?
Given the language L = {ab, aa, baa}, whih of the following strings...
 Which of the following problems are decidable?….1) Does a...
ϵL is equivalent to
How many strings of length less than 4 contains the language described...
 Let w be any string of length n is {0,1}*. Let L be the set of...
 Regular expression are
Alert!

Advertisement