Learn more about our help with Assignments: Math
Search & Filtering
Consider the language defined as follows
L=(0+1)* if man goes to Mars by 2020AD
And
L=0* if man never goes to the Mars
Which of the following is true?
a. L is context free language but not recursive
b. L is recursive
c. Whether L is recursive or not will be known in 2020AD
d. L is a r.e. set that is not regular
L=(0+1)* if man goes to Mars by 2020AD
And
L=0* if man never goes to the Mars
Which of the following is true?
a. L is context free language but not recursive
b. L is recursive
c. Whether L is recursive or not will be known in 2020AD
d. L is a r.e. set that is not regular
Nobody knows yet if P = NP. Consider the language L defined as follows:
L=(0+1)* if P = NP
And
L=j otherwise
Which of the following statements is true?
a) L is recursive
b) L is recursively enumerable but not recursive
c) L is not recursively enumerable
d) Whether L is recursive or not will be known after we find out if P = NP
L=(0+1)* if P = NP
And
L=j otherwise
Which of the following statements is true?
a) L is recursive
b) L is recursively enumerable but not recursive
c) L is not recursively enumerable
d) Whether L is recursive or not will be known after we find out if P = NP
L=(0+1)* if the CSLs are closed under complement and
L=(0*1)*0* if P=NP and
L=(10*)1* if P is not the same as NP
Which of the following is true?
a) L is always regular set
b) L does not exist
c) L is recursive but not a regular set
d) what L will be known after P=NP and the closure of CSLs under complement are resolved
L=(0*1)*0* if P=NP and
L=(10*)1* if P is not the same as NP
Which of the following is true?
a) L is always regular set
b) L does not exist
c) L is recursive but not a regular set
d) what L will be known after P=NP and the closure of CSLs under complement are resolved
Consider two languages L1 and L2 each on the alphabet sigma. Let
f: sigma->sigma be a polynomial time computable bijection such that
( for all x [ x belongs to L1 iff f(x) belongs to L2]. Further, let f1 be also polynomial time
commutable.
Which of the following CANNOT be true?
(A) L1 belongs to P and L2 finite
(B) L1 belongs to NP and L2 belongs to P
(C) L1 is undecidable and L2 is decidable
(D) L1 is recursively enumerable and L2 is recursive
f: sigma->sigma be a polynomial time computable bijection such that
( for all x [ x belongs to L1 iff f(x) belongs to L2]. Further, let f1 be also polynomial time
commutable.
Which of the following CANNOT be true?
(A) L1 belongs to P and L2 finite
(B) L1 belongs to NP and L2 belongs to P
(C) L1 is undecidable and L2 is decidable
(D) L1 is recursively enumerable and L2 is recursive
If the strings of a language L can be effectively enumerated in
lexicographic (i.e. alphabetic) order, which of the following statements
is true?
(A) L is necessarily finite
(B) L is regular but not necessarily finite
(C) L is context free but not necessarily regular
(D) L is recursive but not necessarily context free
lexicographic (i.e. alphabetic) order, which of the following statements
is true?
(A) L is necessarily finite
(B) L is regular but not necessarily finite
(C) L is context free but not necessarily regular
(D) L is recursive but not necessarily context free
Nobody knows yet if P = NP. Consider the language L defined as
follows
L=(0 + 1)* if P = NP
= φ otherwise
Which of the following statements is true?
(A) L is recursive
(B) L is recursively enumerable but not recu
(C) L is not recursively enumerable
(D) Whether L is recursive or not will be known after we find out if
P = NP
follows
L=(0 + 1)* if P = NP
= φ otherwise
Which of the following statements is true?
(A) L is recursive
(B) L is recursively enumerable but not recu
(C) L is not recursively enumerable
(D) Whether L is recursive or not will be known after we find out if
P = NP
Write these numbers in expanded form
2357 431 809
1984 137 075
895 640 267
2357 431 809
1984 137 075
895 640 267
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?
a) Only L2 is context free
b) Only L2 and L3 are context free
c) Only L1 and L2 are context free
d) All are context free
a) Only L2 is context free
b) Only L2 and L3 are context free
c) Only L1 and L2 are context free
d) All are context free
Explain the following statements and determine whether they are true or false.
1) Complement of a CFL need not be recursive
2) If L is recursive then (L)^+ is also recursive.
3) If L1 is recursive and L2 is recursively enumerable then L2 - L1 is need not be recursively enumerable.
4)Recursive sets are closed under complement and substitution.
1) Complement of a CFL need not be recursive
2) If L is recursive then (L)^+ is also recursive.
3) If L1 is recursive and L2 is recursively enumerable then L2 - L1 is need not be recursively enumerable.
4)Recursive sets are closed under complement and substitution.
Consider the following languages
L1 = { 0^p 1^q 0^r | p,q,r >=0 }
L2 = { 0^p 1^q 0^r | p,q,r >=0, p != r }
Determine whether they are regular or context-free.
L1 = { 0^p 1^q 0^r | p,q,r >=0 }
L2 = { 0^p 1^q 0^r | p,q,r >=0, p != r }
Determine whether they are regular or context-free.
"assignmentexpert.com" is professional group of people in Math subjects! They did assignments in very high level of mathematical modelling in the best quality. Thanks a lot
#339914 on Dec 2023
#339914 on Dec 2023