Scribd Logo
Upload

Welcome to Scribd!

  • 54 views

    AUTOMATA

    Uploaded by

    Vinay Kumar Gupta
    (1) The language {ambmcm | m >=0} is not a context-free language. This can be shown by using the pumping lemma to obtain a contradiction with strings of the form aPbPcP where P is greater than the number of variables in the grammar. (2) The language {0n1m2n+m | m, n >=0} is a context-free language. The corresponding grammar is S → 0S2 | S1, S1 → 1S12 | ε. (3) The language generated by the grammar S → aSc | b is {anbnc^n | n >= 0}. A pushdown automaton can

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    AUTOMATA

    Uploaded by

    Vinay Kumar Gupta
    54 views2 pages
    (1) The language {ambmcm | m >=0} is not a context-free language. This can be shown by using the pumping lemma to obtain a contradiction with strings of the form aPbPcP where P is greater than the number of variables in the grammar. (2) The language {0n1m2n+m | m, n >=0} is a context-free language. The corresponding grammar is S → 0S2 | S1, S1 → 1S12 | ε. (3) The language generated by the grammar S → aSc | b is {anbnc^n | n >= 0}. A pushdown automaton can

    Original Description:

    QUESTION OF TM

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    (1) The language {ambmcm | m >=0} is not a context-free language. This can be shown by using the pumping lemma to obtain a contradiction with strings of the form aPbPcP where P is greater than the number of variables in the grammar. (2) The language {0n1m2n+m | m, n >=0} is a context-free language. The corresponding grammar is S → 0S2 | S1, S1 → 1S12 | ε. (3) The language generated by the grammar S → aSc | b is {anbnc^n | n >= 0}. A pushdown automaton can

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    54 views2 pages

    AUTOMATA

    Uploaded by

    Vinay Kumar Gupta
    (1) The language {ambmcm | m >=0} is not a context-free language. This can be shown by using the pumping lemma to obtain a contradiction with strings of the form aPbPcP where P is greater than the number of variables in the grammar. (2) The language {0n1m2n+m | m, n >=0} is a context-free language. The corresponding grammar is S → 0S2 | S1, S1 → 1S12 | ε. (3) The language generated by the grammar S → aSc | b is {anbnc^n | n >= 0}. A pushdown automaton can

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 2

    Please Attach This Question Paper on Top of Your Answer Sheets Type Your Name Here:

    CSE 5210 Formal Languages and Automata Theory Exam 2 Points 50 Time 70 min

    Spring 2011

    While developing a machine do not forget to write some description/logic behind your design.

    (1) Prove in your own language the following language {ambmcm , m >=0} is not in CFL. [10] This is already in notes/text. Hence, your own language. Assume a Chomsky Normal Form CFG generates this with N variables. Take a string in the language aPbPcP, where P>2^N. Then run pumping lemma for all cases to show a string with unbalanced number of as, bs and c,s should be generated by the grammar. This contradiction invalidates the assumption of any feasible CFG. (2) Is the following language {0n1m2n+m , m, n >=0} CFL? If yes write the corresponding grammar, if not prove your assertion by using pumping lemma. [10] n m m n Yes. View this as 0 (1 2 )2 . S -> 0 S 2 | S1, S1 -> 1 S1 2 | e (3) The following is a CFG over sigma={a,b,c}: S -> aSc | b What is the language that it generates? Develop a PDA for the language? [10] n n Language is {a b c , for n>= 0}. Push for as, change state at, and pop for cs. End of string must be at the stack bottom. If stack bottom of end of string is not arrived simultaneously machine has no transition. Be careful with case n=0. (4) Develop a Turing Machine for a language of strings that does not end with 0, over sigma={0,1,2} [10] Scan through all characters, change state after end of string and move left. No transition on that last character being 0. If it is 1 or 2, arrive at final state. (5) For two languages L and L1 define/explain the followings concisely: L = L1 L L1 L is a proper subset of L1 L is a recursive language L is a recursively enumerable language but not recursive [10] Each element of L is also in L1. Each element of L1 is also in L.

    Some element of L is not in L1, or some element of L1 is not in L. Each element of L is in L1, but some element of L1 is not in L. There exists a Turing machine that halts for all strings over sigma, but accepts only the strings in L. There exist a Turing machine that halts and accepts all strings in L, but there exist no Turing machine that halts for all strings not in L.

    You might also like