Scribd Logo
Upload

Welcome to Scribd!

  • 229 views

    Context Free Grammar

    Uploaded by

    Seaton Harns
    This document provides solutions to 7 problems related to context-free grammars (CFGs) and pushdown automata (PDAs). The problems involve generating languages from CFGs, writing CFGs for regular expressions, checking for ambiguity in CFGs, and constructing PDAs for specific languages. The solutions demonstrate how to determine languages from CFGs, write grammars, find ambiguous parses, and build automata to recognize languages with certain properties over the alphabets {a,b,c}.

    Copyright:

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

    Context Free Grammar

    Uploaded by

    Seaton Harns
    229 views2 pages
    This document provides solutions to 7 problems related to context-free grammars (CFGs) and pushdown automata (PDAs). The problems involve generating languages from CFGs, writing CFGs for regular expressions, checking for ambiguity in CFGs, and constructing PDAs for specific languages. The solutions demonstrate how to determine languages from CFGs, write grammars, find ambiguous parses, and build automata to recognize languages with certain properties over the alphabets {a,b,c}.

    Original Description:

    CONTEXT FREE GRAMMAR

    Original Title

    CONTEXT FREE GRAMMAR

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides solutions to 7 problems related to context-free grammars (CFGs) and pushdown automata (PDAs). The problems involve generating languages from CFGs, writing CFGs for regular expressions, checking for ambiguity in CFGs, and constructing PDAs for specific languages. The solutions demonstrate how to determine languages from CFGs, write grammars, find ambiguous parses, and build automata to recognize languages with certain properties over the alphabets {a,b,c}.

    Copyright:

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

    Context Free Grammar

    Uploaded by

    Seaton Harns
    This document provides solutions to 7 problems related to context-free grammars (CFGs) and pushdown automata (PDAs). The problems involve generating languages from CFGs, writing CFGs for regular expressions, checking for ambiguity in CFGs, and constructing PDAs for specific languages. The solutions demonstrate how to determine languages from CFGs, write grammars, find ambiguous parses, and build automata to recognize languages with certain properties over the alphabets {a,b,c}.

    Copyright:

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

    CS5104 Assignment 4

    Due: Wednesday, April 7


    1. Consider the CFG
    S ~ aX
    X ~ aX,bX,
    What is the language this CFG generates?
    Solution:
    a(ab)*
    2. Consider the CFG
    S ~ XaXaX
    X ~ aX,bX,
    What is the language this CFG generates?
    Solution:
    (ab)*a(ab)*a(ab)*
    3. Find a CFG Ior each oI the languages deIined by the Iollowing regular expressions:
    a. ab*
    b. a*b*
    c. (baa abb)*
    Solutions:
    a) S -~ a , Sb
    b) S -~ XY
    X -~ aX ,
    Y -~ bY ,
    c) S -~ SS , baa , abb ,
    4. Write a CFG to generate the language MOREA oI all strings that have more a`s than
    b`s.
    Solution:
    S -~ SS , EXE
    X -~ aX , a
    E -~ aB , bA
    A -~ a , aS , bAA
    B -~ b , bS , aBB
    5. Show that the Iollowing CFGs are ambiguous by Iinding a word with two distinct
    parse trees.
    i. S ~ SaSaS,b
    ii. S ~ aSb,Sb,Sa,a.
    Solution:
    i) babababab
    ii) aab
    6. Build a PDA Ior the language a
    n
    b
    m
    a
    m
    b
    n
    , n ~ 0 and m ~ 0}
    7. Build a PDA Ior the language a
    2n
    b
    n
    , n ~ 0}
    8. Build a PDA Ior the language a
    l
    b
    m
    c
    n
    , l, m, n ~ 0 and l m n}

    You might also like