Formal Language & Automata Theory

1. A regular language over an alphabet a is one that can be obtained from

Union

Concatenation

Kleene

All of above

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

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

2. Regular expressions are closed under

Union

Intersection

Kleen star

All of the mentioned

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.

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.

3. A language is regular if and only if

Accepted by DFA

Accepted by PDA

Accepted by LBA

Accepted by Turing machine

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.

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.

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

0 U 1

0 / 1

0 + 1

All of above

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

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

5. Number of states require to accept string ends with 10.

3

2

1

Can’t be represented.

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.

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.

6. Finite automata requires minimum _______ number of stacks.

1

0

2

None of the mentioned

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.

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.

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

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.

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.

8. 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!

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.

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.

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

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.

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.

10. ΦL is equivalent to

LΦ

Φ

ϵ

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.

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.

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

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

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

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

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

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.

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.

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?

L2 – L1 is recursively enumerable.

L1 – L3 is recursively enumberable

L2 \cap L1 is recursively enumberable

L2 \cup L1 is recursively enumberable

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.

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.

14. 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=Ø

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.

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.

15. 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?

Only L2 is context free

Only L2 and L3 are context free

Only L1 and L2 are context free

All are context free

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.

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.

16. 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?

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

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.

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.

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

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.

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.

18. Language of finite automata is.

Type 0

Type 1

Type 2

Type 3

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.

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.

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

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.

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. Regular expression Φ* is equivalent to

ϵ

Φ

0

1

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

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

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

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.

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.

22. L and ~L are recursive enumerable then L is

Regular

Context free

Context sensitive

Recursive

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.

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.

23. (a+b)* is equivalent to

B*a*

(a*b*)*

A*b*

None of above

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.

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.

24. Consider following regular expression
i) (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

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.

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.

25. 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?

(0*10*1)*

0*(10*10*)*

0*(10*1*)*0*

0*1(10*1)*10*

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.

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.

26. a? is equivalent to

A

A+Φ

A+ϵ

Wrong expression

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.

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.

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

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.

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.

28. Precedence of regular expression in decreasing order is

* , . , +

. , * , +

. , + , *

+ , a , *

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.

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.

29. 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+

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.

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.

30. 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)*

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.

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.

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

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.

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.

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

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.

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.

33. ϵL is equivalent to

ϵ

Φ

L

Lϵ

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.

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.

34. 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 {pⁿqⁿ|n $\in$ N}). Then which of the following is ALWAYS regular?

P Q

P – Q

* – P

* – Q

The expression "* - P" is always regular because when we subtract a regular language from any language, the resulting language 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.

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

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.

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.

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

not-available-via-ai

Explanation

not-available-via-ai

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

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.

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.

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

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.

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.

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?

N-1

N

N+1

2n-1

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.

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.

40. Regular expression are

Type 0 language

Type 1 language

Type 2 language

Type 3 language

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.

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.

Formal Language & Automata Theory

What do you like, dislike, and how can we improve?