Other Math Answers

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.

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.

Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.

Consider the languages
L1= {a^n b^n c^m | n,m > 0} and L2= {a^n b^m c^m | n,m > 0}

(A) L1 intersection L2 is a context-free language
(B) L1 union L2 is a context-free language
(C) L1 and L2 are context-free language
(D) L1 intersection L2 is a context sensitive language

What is the language {a^m b^(m+n) | m,n >= 1} ? Explain.

(A) regular
(B) context-free but not regular
(C) context sensitive but not context free
(D) type-0 but not context sensitive

Which of the following are decidable?
1. Whether the intersection of two regular languages is infinite
2. Whether a given context-free language is regular
3. Whether two push-down automata accept the same language
4. Whether a given grammar is context-free
(A) 1 and 2 (B) 1 and 4
(C) 2 and 3 (D) 2 and 4

Which of the following is true for the language{a^P | P is a prime} and why?
(A) It is not accepted by a Turning Machine
(B) It is regular but not context-free
(C) It is context-free but not regular
(D) It is neither regular nor context-free, but accepted by a Turing machine

Which of the following languages is regular?
(A) {WW^R |W belongs to {0,1}^+}
(B) {WW^RX | X,W belongs to {0,1}^+}
(C) {WXW^RX | X,W belongs to {0,1}^+}
(D) {XWW^RX | X,W belongs to {0,1}^+}

The language L = {0^i 21^i | i <= 0} over the alphabet {0,1,2} is
(A) not recursive
(B) is recursive and is a deterministic CFL
(C) us a regular language
(D) is not a deterministic CFI but a CFL

If the entire program is written in FORTRAN, the percentage increase in the execution time, compared to writing the entire program in FORTRAN and rewriting the 1% in assembly language is
a) 0.9
b) 0.8
c) 8
d) 9