Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    ATC Question Bank

    Uploaded by

    bibliophileonthesamepage
    All the modules question bank for the subject, automatic theory and computation fifth semester, VTU

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    ATC Question Bank

    Uploaded by

    bibliophileonthesamepage
    19 views2 pages
    All the modules question bank for the subject, automatic theory and computation fifth semester, VTU

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    All the modules question bank for the subject, automatic theory and computation fifth semester, VTU

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    19 views2 pages

    ATC Question Bank

    Uploaded by

    bibliophileonthesamepage
    All the modules question bank for the subject, automatic theory and computation fifth semester, VTU

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    1.

    Obtain an FSM which accepts strings of a’s and b’s star9ng with ab
    2. Obtain an NFA for Regular Expression a*+b*+c*
    3. Obtain NFA for RE (a+b)*aa(a+b)*
    4. Obtain grammar to generate strings consis9ng of any number of a’s.
    5. Obtain grammar to generate strings consis9ng of at least one a’s.
    6. List and explain the Chomsky hierarchy and their proper9es.
    7. Obtain grammar to generate strings consis9ng of any number of a’s and b’s.
    8. Obtain grammar to generate strings consis9ng of at least two a’s.
    9. Obtain grammar to generate strings consis9ng of even number of a’s.
    10. Obtain grammar to generate strings consis9ng of mul1ples of 3a’s.
    11. Obtain grammar to generate strings consis9ng of a’s and b’s such that the string length is
    mul1ple of 3.
    12. Obtain grammar to generate strings consis9ng of any number of a’s and b’s with at least one
    a.
    13. Obtain grammar to generate strings consis9ng of at least one a or at least one b
    14. Obtain grammar which accepts strings of a’s and b’s ending with ab
    15. Obtain grammar which accepts strings of a’s and b’s star9ng with ab
    16. State and prove pumping lemma theorem
    17. Show that L={wwR | w belongs to (0+1)*} is not regular
    18. Show that L={anbn : n>=0} is not regular
    19. Show that L={ aibj : i>j} is not regular
    20. Show that L={ an! | n>=0} is not regular
    21. Show that L={w | na(w)< nb(w)} is not regular
    22. Prove the property closure under union
    23. Prove the property closure under intersec9on
    24. Prove the property closure under union
    25. Prove the property closure under complementa9on
    26. Prove the property closure under reversal
    27. Let ∑ = {0,1} ⌠={0,1,2} and h(0)=01, h(1)=112. What is h(010)? If L={00,010} what is the
    homorphic image of L?
    28. ∑ = {0,1} ⌠={1,2,3}, h(0)=3122, h(1)=132. What is (0+1)*(00)*
    29. Obtain lecmost and rightmost deriva9on for the string id+id*id for the grammar from which
    any arithme9c expression can be obtained.
    30. Obtain lec most deriva9on for the string aaabbabbba using the following grammar
    S-> aB | bA
    A-> aS | bAA | a
    B-> bS | aBB | b
    31. Obtain language for the grammar
    S-> aCa
    C-> aCa | b
    32. Obtain grammar to generate the following languages
    1. L={anbn : n>=0}
    2. L={anbn : n>=1}
    3. L={an+1bn : n>=0}
    4. L={anbn+1 : n>=0}
    5. L={anbn+2 : n>=0}
    6. L={anb2n: n>=0}
    7. L={set of all palindromes over ∑ = {a,b} }
    8. L={wwR: w belongs to {a,b}*}
    9. Language consis9ng of all non palindromes over a,b
    10. L={0m1m2n: m>=n, n>=0}
    11. L={w | na(w) = nb(w)}
    12. To generate strings of balanced parenthesis
    13. L={0i1j | i!=j, i>=0 and j>=0}
    14. L={an+2bm : n>=0 and m>n}
    15. L={anbm : n>=0, m>n}
    16. L=L1L2, L1={anbm : n>=0, m>n} and L2={0n12n : n>=0}
    17. L=L1 U L2, L1={anbm : n>=0, m>n} and L2={0n12n : n>=0}
    18. Language of strings of 0’s and 1’s having substring 000
    19. L={anbncn: m,n>=0}
    33. Show that the grammar is ambiguous for the following grammar:
    1. E-> E + E | E – E
    E-> E * E | E / E | (E) |id
    String: id+id*id
    2. S-> aS | X
    X-> aX | a
    String: aaaa
    3. S-> iCtS | iCtSeS | a
    C-> b
    String: ib9btaea
    4. S-> aB | bA
    A-> aS | bAA | a
    B-> bS | aBB | b
    String: aaabbabbba
    5. S-> AB | aaB
    A-> a |Aa
    B-> b
    String: aab
    6. S-> aSbS
    S-> bSaS
    S-> €
    String: aababb
    34. Convert the following grammar into CNF
    S-> 0A | 1B
    A-> 0AA | 1S | 1
    B-> 1BB | 0S | 0
    35. Convert the following grammar into GNF
    S-> AB1 | 0
    A-> 00A | B
    B-> 1A1
    36. Design PDA for accep9ng the languages
    1. L={anb2n : n>=1}
    2. L={anbn : n>=1}
    3. L={wwR | W belongs to {a,b}*}
    4. L={wCwR | W belongs to {a,b}*}
    5. L={0n1m0n | m,n >= 1}

    You might also like