Context-Sensitive Languages: Questions
  1. Consider the following grammar with start symbol S:


    2. S -> FM
    F -> FaA
    F -> FbB
    F -> aA
    F -> bB
    Aa -> aA
    Ab -> bA
    Ba -> aB
    Bb -> bB
    AM -> Ma
    BM -> Mb
    M -> c

    Indicate whether or not the following strings belong to this language:

    1. c
    2. aca
    3. acb
    4. bcb
    5. abcab
    6. abcba
    7. bacba
    8. bacab
    9. aacaa
    10. aacbb

  2. Consider the linear bounded automaton with start state s and the following transitions:


    3. ((s,<),(t,<,R))
    ((t,a),(u,x,R))
    ((t,b),(v,x,R))
    ((t,x),(t,x,Y))
    ((t,>),(t,>,Y))
    ((u,a),(u,a,R))
    ((u,b),(u,b,R))
    ((u,x),(w,x,L))
    ((u,>),(w,>,L))
    ((v,a),(v,a,R))
    ((v,b),(v,b,R))
    ((v,x),(x,x,L))
    ((v,>),(x,>,L))
    ((w,a),(y,x,L))
    ((w,x),(w,x,Y))
    ((x,b),(y,x,L))
    ((x,x),(x,x,Y))
    ((y,a),(y,a,L))
    ((y,b),(y,b,L))
    ((y,x),(t,x,R))

    Indicate whether or not the following strings belong to this language:

    1. aa
    2. ab
    3. bb
    4. aba
    5. abba
    6. abab
    7. aaaa
    8. bbbb
    9. baab
    10. baba