Toc Quiz Questions And Answers

1. Define FOUR (w) for a finite string w, to be the string consisting of the symbols of w in positions that are multiples of four. For example, FOUR (1110011100) = 01. If L is a regular language, then { FOUR (w): w є L} must be regular.

True

False

Can't say

None of these

The given statement is true. If L is a regular language, then { FOUR (w): w є L} must also be regular. This is because regular languages are closed under homomorphism, which means that applying a homomorphism to a regular language will result in another regular language. In this case, the homomorphism is the function FOUR, which takes a string and returns a new string consisting of only the symbols in positions that are multiples of four. Since regular languages are closed under homomorphism, the resulting language { FOUR (w): w є L} will also be regular.

Explanation

The given statement is true. If L is a regular language, then { FOUR (w): w є L} must also be regular. This is because regular languages are closed under homomorphism, which means that applying a homomorphism to a regular language will result in another regular language. In this case, the homomorphism is the function FOUR, which takes a string and returns a new string consisting of only the symbols in positions that are multiples of four. Since regular languages are closed under homomorphism, the resulting language { FOUR (w): w є L} will also be regular.

2. If L is a language over an alphabet, ∑ let NoPrefix(L) = {x є L: no proper prefix of x is in L}. If L is regular, then so is NoPrefix(L).

True

False

Can't Say

None of these

If a language L is regular, it means that there exists a regular expression, finite automaton, or regular grammar that can generate L. In this case, NoPrefix(L) is a subset of L that contains all the words in L that do not have any proper prefixes that are also in L. Since L is regular, it can be generated by a regular expression, finite automaton, or regular grammar. We can modify this regular expression, finite automaton, or regular grammar to generate NoPrefix(L) instead by simply excluding any words with proper prefixes that are also in L. Therefore, NoPrefix(L) is also regular.

Explanation

If a language L is regular, it means that there exists a regular expression, finite automaton, or regular grammar that can generate L. In this case, NoPrefix(L) is a subset of L that contains all the words in L that do not have any proper prefixes that are also in L. Since L is regular, it can be generated by a regular expression, finite automaton, or regular grammar. We can modify this regular expression, finite automaton, or regular grammar to generate NoPrefix(L) instead by simply excluding any words with proper prefixes that are also in L. Therefore, NoPrefix(L) is also regular.

3. Read the following statements1) For every NFA with an arbitrary no. of final states there is an equivalent NFA with only one final state2) Regular sets are closed under infinite union3) Regular sets are closed under the prefix Which of the following is true?

1 & 3 are only correct statements

1, 2 & 3 statements are correct

1 is the only correct statement

None of the above is correct

The statement "For every NFA with an arbitrary no. of final states there is an equivalent NFA with only one final state" is true because it is possible to convert an NFA with multiple final states into an equivalent NFA with only one final state by adding a new final state and redirecting all transitions from the original final states to the new final state.

The statement "Regular sets are closed under the prefix" is also true because if a language is regular, then all its prefixes are also regular. This is because adding any finite number of symbols to the beginning of a regular language will still result in a regular language.

Explanation

The statement "For every NFA with an arbitrary no. of final states there is an equivalent NFA with only one final state" is true because it is possible to convert an NFA with multiple final states into an equivalent NFA with only one final state by adding a new final state and redirecting all transitions from the original final states to the new final state.

The statement "Regular sets are closed under the prefix" is also true because if a language is regular, then all its prefixes are also regular. This is because adding any finite number of symbols to the beginning of a regular language will still result in a regular language.

4. Convert the following DFA into a regular expression

0*10*1 (0 U 10*10*1)*

10* (0 U 10*10*1)* 10*

(0 U 10*10*1)* 0*10*1

None of the above

The correct answer is "0*10*1 (0 U 10*10*1)*" because it represents a regular expression that matches strings that start with zero or more 0s, followed by a 1, followed by zero or more 1s, and then repeats the pattern of zero or more 0s followed by a 1, zero or more times. This regular expression accurately represents the language accepted by the given DFA.

Explanation

The correct answer is "0*10*1 (0 U 10*10*1)*" because it represents a regular expression that matches strings that start with zero or more 0s, followed by a 1, followed by zero or more 1s, and then repeats the pattern of zero or more 0s followed by a 1, zero or more times. This regular expression accurately represents the language accepted by the given DFA.

5. The pumping lemma for regular languages can be used to

Prove that a given language is regular

Prove that a given language is not regular

Prove that all CFLs have a corresponding PDA

Prove that a given CFL is inherently ambiguous

The pumping lemma for regular languages is a tool used to prove that a given language is not regular. It states that for any regular language, there exists a pumping length such that any string in the language longer than the pumping length can be divided into five parts, where the middle three parts can be repeated any number of times. By applying the pumping lemma, if we can show that a language cannot satisfy this property, we can conclude that it is not regular. Therefore, the pumping lemma can be used to prove that a given language is not regular.

Explanation

The pumping lemma for regular languages is a tool used to prove that a given language is not regular. It states that for any regular language, there exists a pumping length such that any string in the language longer than the pumping length can be divided into five parts, where the middle three parts can be repeated any number of times. By applying the pumping lemma, if we can show that a language cannot satisfy this property, we can conclude that it is not regular. Therefore, the pumping lemma can be used to prove that a given language is not regular.

6. A finite state machine with the following states table has a single input x & single output z. If the initial state is unknown, then the shortest input sequence to reach the final state C is

01

10

110

101

The shortest input sequence to reach the final state C is "01" because the finite state machine transitions from the initial state to state C when the input sequence is "01".

Explanation

The shortest input sequence to reach the final state C is "01" because the finite state machine transitions from the initial state to state C when the input sequence is "01".

7. Which of the following is true

A(ab)*a = a(ba)* & (P*Q*) = (P*+Q*)*

(a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)*

(a+b)*ab[(a+b)*ab(a+b)*+b*a*+b*a*] = (a+b)*

None of the above

The given equation (a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)* states that any string consisting of a or b, followed by any number of a's and b's, followed by any number of a's and b's, followed by any number of a's and b's, is equal to any string consisting of a or b, followed by any number of a's and b's, followed by ab, followed by any number of a's and b's. This is true because both sides of the equation represent the same language, which is the set of all possible strings that can be formed using a and b.

Explanation

The given equation (a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)* states that any string consisting of a or b, followed by any number of a's and b's, followed by any number of a's and b's, followed by any number of a's and b's, is equal to any string consisting of a or b, followed by any number of a's and b's, followed by ab, followed by any number of a's and b's. This is true because both sides of the equation represent the same language, which is the set of all possible strings that can be formed using a and b.

8. Which of the following statements is true?i) If L is a regular language, then LR is also a regular languageii) If L is a regular language, then L2 may not be a regular languageiii) The grammar {G = ({S}, {a}, S, {S->Saaa | aS| a})} is not regulariv) The grammar {G = ({S}, {a, b}, S, {S->aS | bS| })} is not regular

I only

I and iii and iv only

Ii, iii, and iv only

Iii and iv only

The statement "If L is a regular language, then LR is also a regular language" is true. This means that if L is a regular language, then the language formed by reversing all the strings in L (denoted as LR) is also regular. This property holds for regular languages and can be proven using various methods such as constructing a finite automaton or using regular expressions.

Explanation

The statement "If L is a regular language, then LR is also a regular language" is true. This means that if L is a regular language, then the language formed by reversing all the strings in L (denoted as LR) is also regular. This property holds for regular languages and can be proven using various methods such as constructing a finite automaton or using regular expressions.

9. Which of the following statement is true?

The language { : n >= 0, n !=4} is regular

The set of all real numbers is a regular language.

The language { : n = i+ jk; i, k fixed, j=0,1,2………….} is regular

All of the above

All of the given statements are true.

The language {: n >= 0, n !=4} is regular because it can be represented by a regular expression or a deterministic finite automaton.

The set of all real numbers is a regular language because it can be represented by a regular expression or a deterministic finite automaton.

The language {: n = i+ jk; i, k fixed, j=0,1,2………….} is regular because it can also be represented by a regular expression or a deterministic finite automaton.

Therefore, the correct answer is "All of the above".

Explanation

All of the given statements are true.

The language {: n >= 0, n !=4} is regular because it can be represented by a regular expression or a deterministic finite automaton.

The set of all real numbers is a regular language because it can be represented by a regular expression or a deterministic finite automaton.

The language {: n = i+ jk; i, k fixed, j=0,1,2………….} is regular because it can also be represented by a regular expression or a deterministic finite automaton.

Therefore, the correct answer is "All of the above".

10. Which of the set can be recognized by DFS automata

The no. 1,2,4,…………….2n,………..written in binary

The set {1, 101, 11011,1110111…}

The no. 1,2,4,……………. ,………..written in unary

The set of binary strings in which the no. of 0’s is the same as the no. of 1’s

The set of numbers 1, 2, 4, ..., 2n, ... written in binary can be recognized by a Depth First Search (DFS) automata. This is because the binary representation of these numbers follows a pattern where each number is obtained by multiplying the previous number by 2. A DFS automata can traverse through this pattern by exploring all possible paths and backtracking when necessary. Therefore, it can recognize this set of numbers.

Explanation

The set of numbers 1, 2, 4, ..., 2n, ... written in binary can be recognized by a Depth First Search (DFS) automata. This is because the binary representation of these numbers follows a pattern where each number is obtained by multiplying the previous number by 2. A DFS automata can traverse through this pattern by exploring all possible paths and backtracking when necessary. Therefore, it can recognize this set of numbers.

11. Let r = 1(1+0)*, s= 11* 0 & t= 1*0 be 3 regular expression as which one of the following is true

L(s) L(r) & L(s) L (t)

L(r) L(s) & L(s) L (t)

L (t) L(s) & L(r) L(s)

L (t) L(s) & L(s) L(r)

The correct answer is L(s) L(r) & L(s) L (t). This means that the language generated by regular expression s concatenated with the language generated by regular expression r is equal to the language generated by regular expression s concatenated with the language generated by regular expression t.

Explanation

The correct answer is L(s) L(r) & L(s) L (t). This means that the language generated by regular expression s concatenated with the language generated by regular expression r is equal to the language generated by regular expression s concatenated with the language generated by regular expression t.

12. Regular expression corresponding to the following FA will be

(ab + aaa*b)*(a+ )

(ab + aaa*b)*

(a + aaa*b)* (a+ )

None of the above

The regular expression (ab + aaa*b)*(a+) corresponds to the given finite automaton (FA). This regular expression represents a language that consists of any number of occurrences of the pattern "ab" or "aaa*b" followed by one or more occurrences of "a". The asterisk (*) denotes zero or more occurrences, and the plus sign (+) denotes one or more occurrences. Therefore, this regular expression captures all possible strings that can be accepted by the given FA.

Explanation

The regular expression (ab + aaa*b)*(a+) corresponds to the given finite automaton (FA). This regular expression represents a language that consists of any number of occurrences of the pattern "ab" or "aaa*b" followed by one or more occurrences of "a". The asterisk (*) denotes zero or more occurrences, and the plus sign (+) denotes one or more occurrences. Therefore, this regular expression captures all possible strings that can be accepted by the given FA.

13. The language accepted by push down automaton in which the stack is limited to 10 items is best described as

Context Free

Regular

Deterministic Context free

Recursive

A push down automaton is a type of automaton that uses a stack to store information. In this question, the stack is limited to only 10 items. Regular languages are a type of language that can be recognized by a finite state machine, which is a simpler type of automaton compared to a push down automaton. Since the language accepted by the push down automaton in this case can be recognized by a simpler type of automaton (finite state machine), it is best described as a regular language.

Explanation

A push down automaton is a type of automaton that uses a stack to store information. In this question, the stack is limited to only 10 items. Regular languages are a type of language that can be recognized by a finite state machine, which is a simpler type of automaton compared to a push down automaton. Since the language accepted by the push down automaton in this case can be recognized by a simpler type of automaton (finite state machine), it is best described as a regular language.

14. The finite state machine is described by the following state diagram with A as starting state where an arc label is x/y and, x stands for 1-bit input & y stands for 2-bit output.

Output 01 whenever the input sequence contains 11

Output 10 whenever the input sequence contains 10

Output the sum of the present and previous bits of the input

None of the above

The correct answer is "Output the sum of the present and previous bits of the input" because the state diagram does not have any arcs labeled with specific input sequences like "11" or "10". Instead, it has arcs labeled with "x/y" where "x" represents a 1-bit input and "y" represents a 2-bit output. This indicates that the machine should output the sum of the present and previous bits of the input, regardless of the specific input sequence.

Explanation

The correct answer is "Output the sum of the present and previous bits of the input" because the state diagram does not have any arcs labeled with specific input sequences like "11" or "10". Instead, it has arcs labeled with "x/y" where "x" represents a 1-bit input and "y" represents a 2-bit output. This indicates that the machine should output the sum of the present and previous bits of the input, regardless of the specific input sequence.

15. Consider the language defined by the regular expression (a + b)*b⁺. Which of the following regular expressions also defines that language?

(a*b+) + (b*b+)

(ab + bb)* b*

(a + b + ba)*b+

Both a and c

The correct answer is (a + b + ba)*b+. This regular expression defines the language where any combination of 'a', 'b', and 'ba' can occur any number of times, followed by one or more 'b'. This includes strings like 'b', 'ab', 'bab', 'baab', 'abab', etc. The other options do not cover all the possible combinations and repetitions of 'a', 'b', and 'ba' as specified in the given regular expression.

Explanation

The correct answer is (a + b + ba)*b+. This regular expression defines the language where any combination of 'a', 'b', and 'ba' can occur any number of times, followed by one or more 'b'. This includes strings like 'b', 'ab', 'bab', 'baab', 'abab', etc. The other options do not cover all the possible combinations and repetitions of 'a', 'b', and 'ba' as specified in the given regular expression.

16. Consider the following FAs. Which of the following is true?

FA1 FA2

FA2 FA1

FA1 = FA2

None of the above

The correct answer is "FA2 FA1". This means that the FA2 comes before FA1. In the context of finite automata, the order of the automata can be important in determining the behavior or properties of the system.

Explanation

The correct answer is "FA2 FA1". This means that the FA2 comes before FA1. In the context of finite automata, the order of the automata can be important in determining the behavior or properties of the system.