Other Math Answers

The intersection of two csls can simulate an arbitrary turing machine computation, and this can be used to show some problems are undecidable. The intersection of two csls is (choose the false statement)
a. never a recursive set
b. never a cfl
c. never a csl
d. always not r.e.

A language denoted by extended regular expressions which is regular expressions with the operations of intersection and complementation is
A. regular
B.deterministic context-free but not regular
C. context-sensitive but not context-free
D. type 0 but not context sensitive

A language denoted by a semi-extended regular expression which is regular expression with the additional operation of intersection of regular expressions is
A. regular
B.context-free but not regular
C. context-sensitive but not context-free
D. type 0 but not context sensitive

The languge {0^1 1^j|gcd(i,j)=1} is
A. regular and not infinite
B. context-free but regular
C. context-sensitive but not context-free
D.recursive but not context-sensitive

The language {a^i b^j c^k|i+j>=k} is
A. regular but not finite
B. context-free but not regular
C. context-sensitive but not context-free
D.type-0 or recursive but not context-sensitive

The language {a^i b^j c^k|i<j<k} is
A. regular but not finite
B. context-free but not regular
C. context-sensitive but not context-free
D.recursive or type-0 but not context-sensitive

The language {a^i b^j c^k| k= max(i,j)} os
A. regular but not context-free
B. context-free but not regular
C. context-sensitive but not context-free
D.recursive but not context-sensitive

The language {a^i b^j c^k|k=min(i,j)} is
A. regular but not finite
B. context-free but deterministic context free
C. context-sensitive but not deterministic context-free
D.recursive but not context-sensitive

The language {a^i b^j c^k| i=j or j=k} is
A. regular but not finite
B. deterministic context-free but not regular
C. context-sensitive but not regular
D.type-0 but not context-sensitive

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