Regular languages and Finite automata
Question 1 |
The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________.
a*b*(ba)*a*
3 | |
4 | |
5 | |
6 |
Question 1 Explanation:
The regular expression generate all the strings of length 0 , 1 and 2
{ϵ, a, b, aa, ab, ba, bb}
Let’s check all the string of length 3.
The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}
But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).
{ϵ, a, b, aa, ab, ba, bb}
Let’s check all the string of length 3.
The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}
But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).
Question 2 |
Consider the languages L1 = ϕ and L2 = {a}. Which one of the following represents L1L2* ∪ L1*?
{є} | |
ϕ | |
a* | |
{є,a} |
Question 2 Explanation:
As we know, for any regular expression R,
Rϕ = ϕR=ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
Rϕ = ϕR=ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
Question 3 |
Consider the DFA given.
Which of the following are FALSE?
Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.1 and 3 only | |
2 and 4 only | |
2 and 3 only | |
3 and 4 only |
Question 3 Explanation:
L(A) is regular and its complement is also regular (by closure property) and every regular is CFL also. So Complement of LA is context-free.
The regular expression corresponding to the given FA is
Hence we have regular expression: (11*0 +0) (0+1)*
Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon.
So it is equivalent to (11*0 +0) (0+1)*0*1*
The given DFA can be minimised, since the non-final states are equivalent and can be merged and the min DFA will have two states which is given below:
Hence statement 3 is false.
Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.
The regular expression corresponding to the given FA is
Hence we have regular expression: (11*0 +0) (0+1)*
Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon.
So it is equivalent to (11*0 +0) (0+1)*0*1*
The given DFA can be minimised, since the non-final states are equivalent and can be merged and the min DFA will have two states which is given below:
Hence statement 3 is false.
Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.
Question 4 |
Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language if Lc ∪ Mc is TRUE?
It is necessarily regular but not necessarily context-free. | |
It is necessarily context-free. | |
It is necessarily non-regular. | |
None of the above. |
Question 4 Explanation:
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
Question 5 |
Which of the following statements is TRUE about the regular expression 01*0?
It represents a finite set of finite strings. | |
It represents an infinite set of finite strings. | |
It represents a finite set of infinite strings. | |
It represents an infinite set of infinite strings.
|
Question 5 Explanation:
The given expression01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.
So, given regular expression represents an infinite set of finite strings.
Question 6 |
The language {0n 1n 2n | 1 ≤ n ≤ 106} is
regular | |
context-free but not regular | |
context-free but its complement is not context-free | |
not context-free |
Question 6 Explanation:
In this the value of n is finite then we can be able to construct a finite state automata for this language.
So, given language is regular.
So, given language is regular.
Question 7 |
Consider the non-deterministic finite automaton (NFA) shown in the figure.
State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE? Correction in Question: There is an edge from Z->Y labeled 0 and another edge from Y->Z labeled 1 - in place of double arrowed and no arrowed edges.
L1 = L2 | |
L1 ⊂ L2 | |
L2 ⊂ L1 | |
None of the above |
Question 7 Explanation:
Based on Arden's theorem write the Y and Z in terms of incoming arrows,
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Question 8 |
Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
id + id + id + id | |
id + (id* (id * id)) | |
(id* (id * id)) + id | |
((id * id + id) * id) |
Question 8 Explanation:
Let's draw more than one possible tree for id + id + id + id.
There are 8 questions to complete.