Other Math Answers

The set {0,1,#}+-{b1#b2#…#bn|n>=1} where bi is the binary representation of i is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

The language {w| w is the set of all balanced parenthesis} is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

The language {w| w in {0,1}* and w does not have three consecutive 0′s} is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

{w| w has equal number of a’s and b’s } is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

We are given two context-free languages L1 and L2 and L defined as below
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular

Given an arbitrary context free grammar G, we define L as below.
L=(0+1)* if G is ambiguous
And
L=j if G is not ambiguous
Which of the following is true?
a. L is a context-free language
b. L is recursive but not r.e.
c. What L is depends on whether we can determine if G is ambiguous or not
d. What L is is undecidable

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

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

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

Write these numbers in expanded form

2357 431 809
1984 137 075
895 640 267