DOCX

ASSIGNMENT1KEYX

By Gary Black,2014-07-08 09:42
6 views 0
(II) L IS CONTEXT-FREE, POSSIBLY NOT REGULAR, BUT THEN AGAIN IT MIGHT BE REGULAR ... (IV) L MIGHT NOT EVEN BE CONTEXT-FREE, BUT THEN AGAIN IT MIGHT EVEN BE REGULAR ...

    Assignment#1; Due January 19 at start of class

    Review of Formal Languages

    Consider some language L. For each of the following cases, write in one of (i) through (vi), to

    indicate what you can say conclusively about L’s complexity, where

    (i) L is definitely regular

    (ii) L is context-free, possibly not regular, but then again it might be regular (iii) L is context-free, and definitely not regular

    (iv) L might not even be context-free, but then again it might even be regular (v) L is definitely not regular, and it may or may not be context-free (vi) L definitely is not even context-free

    Follow each answer with example languages A (and B, where appropriate) to back up the

    complexity claims inherent in your answer; and/or state some known closure property that reflects a bound on the complexity of L.

Example.) L = A B, where A and B are both context free, and definitely not regular

L can be characterized by Property (ii), above.

    L is context-free, since the class of context-free languages is closed under union. L can be regular. For example,

    n m n m A = { ab| m ? n }, B = { ab| m ? n },

    n m L = A B = { ab| n, m ? 0 }, which is regular since it can be represented by the regular expression a*b*.

    But L is in general not guaranteed to be regular, e.g., if we just make A and B the same context-

    free, non-regular set, then L = A A = A , which is not regular.

a.) L = A B, where A is not context-free and B is regular

    (iv) nnnRegular: A = abc, B = a*b*c*, L = a*b*c* nnnnnnnContext-Free: A = abcde, B = a*b*c*, L = a*b*c*de nnnnnn Non-Context-Free: A = abc, B = , L = abc

    b.) L = A ,;B, where neither A nor B is context-free

    (iv) nnnnnnRegular: A = abc, B = def, L = nnnnnnnmnnContext-Free: A = abcde, B = def | m<=n, L = de nnnnnnnnn Non-Context-Free: A = abc, B = abc, L = abc

    c.) A = L B, where A is regular and B is not context-free

    (iv) nnnRegular: B = abc, L = a*b*c*, A = a*b*c* nnnnnContext-Free: B = abcd*e*, L = a*b*c*de , A = a*b*c*d*e* nnnnnn Non-Context-Free: B = abcd*e*f*, L = a*b*c*def , A = a*b*c*d*e*f*

d.) A = L ,;B, where A and B are both context-free

    (iv) nnnnRegular: B = ab, L = a*b*, A = ab nnnnnnContext-Free: B = ab, L = ab, A = ab nnnnnnn Non-Context-Free: B = ab, L = a*b* def , A = ab

    e.) A = L B, where A is context-free and B is regular

    (v)

    Regular (NO): If L is regular and B is regular then A must also be regular since

    regular languages are closed under intersection nnnnContext-Free: B = a*b*, L = ab, A = ab nnm nn Non-Context-Free: B = a*b*, L = abc| m<=n, A = ab

    f.) L A, where A is context-free, but not regular

    (iv) nnRegular: A = ab, L = nn2n2nContext-Free: A = ab, L = ab nnn!n! Non-Context-Free: A = ab, L = ab

    Lg.) A = , where A is known to be context free

    (v)

    Regular (NO): Since complement of regular is regular, L would have to be regular nniiContext-Free: A = ab, L = ab| ij {a,b}*ba{a,b}* nnm mnnNon-Context-Free: A = (({a,b}* - abc) ({a,b}* - abc))

    This is just the union of two complements. Both these

    complements are deterministic CFLs and CFLs are closed under

    union. L is then the complement of this. By DeMorgan’s Law, the nnm mnnnnncomplement of this union is abc abc which is abc

Report this document

For any questions or suggestions please email
cust-service@docsford.com