Cse355 Final Exam Questions And
Answers With Verified Solutions 100%
Correct Rated A+
T/F: A sublanguage of a regular language is regular. - ANSWER✔✔FALSE:
Every nonregular language over Σ* is a sublanguage of the regular language Σ*
T/F: A language containing a regular language is regular - ANSWER✔✔FALSE:
Every nonregular language over Σ* contains the regular language ∅
T/F: The intersection of a nonregular language and a regular language cannot be
regular. - ANSWER✔✔FALSE: The intersection of every nonregular language
and the regular language ∅ is ∅.
T/F: The intersection of two non-regular languages is non-regular. -
ANSWER✔✔FALSE: The intersection of the nonregular languages over {0,1}, L1
= {0^n 1^n | n > 0}, and L2 = {1^n 0^n | n > 0} is the regular language ∅.
T/F: If languages A and B are regular, then (A U B)' is also regular. -
ANSWER✔✔TRUE: The class of regular languages are closed under union and
complement, therefore A U B must be regular and (A U B)' must also be regular
T/F: If L1 is regular and L2 is context-free, L1 U L2 is also context-free. -
ANSWER✔✔TRUE: Every regular language is context-free, making L1 context-
free. Since the class of CFLs is closed under Union, L1 U L2 must be context-free.
T/F: Every subset of a context free language is regular. - ANSWER✔✔FALSE:
The statement is false even if we assume it's a proper subset. Let nonregular and
, context-free language L1 = {a^n b^n | n > 0} and L2 = {ε}. Let L3 = L1 U L2 =
{a^n b^n | n >= 0}. We know L3 is CFL and clearly L1 is a proper subset of L3.
T/F: If M is a PDA that never puts more than three symbols on its stack during its
computation, then L(M) is regular. - ANSWER✔✔TRUE: If a PDA uses only
finite amount of memory using its stack, then we can simulate this PDA using an
NFA. A finite number of items in stack leads to a finite number of stack
configurations. Each state in this NFA codes for a state of M and a stack
configuration of M . Then, L(M) must be regular.
T/F: If L1 and L2 are both context-free, (L1 U L2)' is also context-free. -
ANSWER✔✔FALSE: Let L1 = {a^n b^n c^n | n >= 0}' and L2 = ∅. Then (L1 U
L2)' = {a^n b^n c^n | n >= 0}, which is NOT context free. Note that L1 is a CFL
although L1' is not context-free.
You can also use De Morgan's Law to transform the statement to L1' ∩ L2'' and
then mention that the complement of a CFL is not guaranteed to be context-free.
Provide a CFL that its complement is not context-free.
T/F: There is no such CFL L whose complement (L)' is also context-free. -
ANSWER✔✔FALSE: Pick any regular language L, which automatically is
context-free, its complement is a CFL because complement of a regular language is
regular, therefore context-free.
If you used the method shown in lecture to convert (01)* U (10)* into an
equivalent NFA, how many total states and accept states would the machine have?
a) 9 total states, 2 accept states
b) 9 total states, 4 accept states
c) 10 total states, 2 accept states
d) 11 total states, 4 accept states
Answers With Verified Solutions 100%
Correct Rated A+
T/F: A sublanguage of a regular language is regular. - ANSWER✔✔FALSE:
Every nonregular language over Σ* is a sublanguage of the regular language Σ*
T/F: A language containing a regular language is regular - ANSWER✔✔FALSE:
Every nonregular language over Σ* contains the regular language ∅
T/F: The intersection of a nonregular language and a regular language cannot be
regular. - ANSWER✔✔FALSE: The intersection of every nonregular language
and the regular language ∅ is ∅.
T/F: The intersection of two non-regular languages is non-regular. -
ANSWER✔✔FALSE: The intersection of the nonregular languages over {0,1}, L1
= {0^n 1^n | n > 0}, and L2 = {1^n 0^n | n > 0} is the regular language ∅.
T/F: If languages A and B are regular, then (A U B)' is also regular. -
ANSWER✔✔TRUE: The class of regular languages are closed under union and
complement, therefore A U B must be regular and (A U B)' must also be regular
T/F: If L1 is regular and L2 is context-free, L1 U L2 is also context-free. -
ANSWER✔✔TRUE: Every regular language is context-free, making L1 context-
free. Since the class of CFLs is closed under Union, L1 U L2 must be context-free.
T/F: Every subset of a context free language is regular. - ANSWER✔✔FALSE:
The statement is false even if we assume it's a proper subset. Let nonregular and
, context-free language L1 = {a^n b^n | n > 0} and L2 = {ε}. Let L3 = L1 U L2 =
{a^n b^n | n >= 0}. We know L3 is CFL and clearly L1 is a proper subset of L3.
T/F: If M is a PDA that never puts more than three symbols on its stack during its
computation, then L(M) is regular. - ANSWER✔✔TRUE: If a PDA uses only
finite amount of memory using its stack, then we can simulate this PDA using an
NFA. A finite number of items in stack leads to a finite number of stack
configurations. Each state in this NFA codes for a state of M and a stack
configuration of M . Then, L(M) must be regular.
T/F: If L1 and L2 are both context-free, (L1 U L2)' is also context-free. -
ANSWER✔✔FALSE: Let L1 = {a^n b^n c^n | n >= 0}' and L2 = ∅. Then (L1 U
L2)' = {a^n b^n c^n | n >= 0}, which is NOT context free. Note that L1 is a CFL
although L1' is not context-free.
You can also use De Morgan's Law to transform the statement to L1' ∩ L2'' and
then mention that the complement of a CFL is not guaranteed to be context-free.
Provide a CFL that its complement is not context-free.
T/F: There is no such CFL L whose complement (L)' is also context-free. -
ANSWER✔✔FALSE: Pick any regular language L, which automatically is
context-free, its complement is a CFL because complement of a regular language is
regular, therefore context-free.
If you used the method shown in lecture to convert (01)* U (10)* into an
equivalent NFA, how many total states and accept states would the machine have?
a) 9 total states, 2 accept states
b) 9 total states, 4 accept states
c) 10 total states, 2 accept states
d) 11 total states, 4 accept states
