Scribd Logo
Upload

Welcome to Scribd!

  • 670 views

    HW3 Solutions 2017 Spring

    Uploaded by

    Ataush Sabuj
    1. The document provides the answers to 9 questions about formal languages and context-free grammars. 2. The questions cover topics such as finding context-free grammars for specific languages, providing derivations for strings using given grammars, showing that strings are not generated by grammars, and determining if strings are in languages generated by grammars. 3. The answers provide the context-free grammars with their productions or explain why strings cannot be derived/generated by the grammars through examples of attempted derivations.

    Copyright:

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

    HW3 Solutions 2017 Spring

    Uploaded by

    Ataush Sabuj
    670 views4 pages
    1. The document provides the answers to 9 questions about formal languages and context-free grammars. 2. The questions cover topics such as finding context-free grammars for specific languages, providing derivations for strings using given grammars, showing that strings are not generated by grammars, and determining if strings are in languages generated by grammars. 3. The answers provide the context-free grammars with their productions or explain why strings cannot be derived/generated by the grammars through examples of attempted derivations.

    Original Description:

    the subject theory of computations

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document provides the answers to 9 questions about formal languages and context-free grammars. 2. The questions cover topics such as finding context-free grammars for specific languages, providing derivations for strings using given grammars, showing that strings are not generated by grammars, and determining if strings are in languages generated by grammars. 3. The answers provide the context-free grammars with their productions or explain why strings cannot be derived/generated by the grammars through examples of attempted derivations.

    Copyright:

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

    HW3 Solutions 2017 Spring

    Uploaded by

    Ataush Sabuj
    1. The document provides the answers to 9 questions about formal languages and context-free grammars. 2. The questions cover topics such as finding context-free grammars for specific languages, providing derivations for strings using given grammars, showing that strings are not generated by grammars, and determining if strings are in languages generated by grammars. 3. The answers provide the context-free grammars with their productions or explain why strings cannot be derived/generated by the grammars through examples of attempted derivations.

    Copyright:

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

    Introduction to Formal Language, Fall 2017 18-Apr-2017 (Tuesday)

    Homework 3
    Instructor: Prof. Wen-Guey Tzeng Scribe: Amir Rezapour

    1. Find context-free grammars for the language L = an bn , n is not multiple of three.


    Answer.
    A context-free grammar for L is G = ({S}, {a, b}, S, S → ab|aabb|aaaSbbb). 2

    2. Give a derivation tree for w = abbbaabbaba for the grammar


    S → abB,
    A → aaBb,
    B → bbAa,
    A → λ.
    Answer. 2

    3. Find context-free grammars for languages L1 = {an bm : 2n ≤ m ≤ 3n} and L2 =


    {w ∈ {a, b}∗ : na (v) ≥ nb (v), where v is any pref ix of w} with n ≥ 0, m ≥ 0.
    Answer.
    A CFG for L1 is G1 = ({S1 }, {a, b}, S1 , P1 ) with production P1 as:
    S1 → aS1 bb|aS1 bbb|λ

    A CFG for L2 is G2 = ({S2 }, {a, b}, S2 , P2 ) with production P2 as:


    S2 → |aS2 b|S2 S2 |λ

    1-1
    2

    For example, for w = aaababbb we can use the grammar for derivation as follows:
    S2 ⇒ aS2 b ⇒ aaS2 S2 bb ⇒ aaaS2 bS2 bb ⇒ aaabaS2 bbb ⇒ aaababbb. Since we only
    allow string start with a’s, any prefix v of a string w has na (v) ≥ nb (v). For example,
    v = a, aa, aaa, aaab, aaaba, aaabab, aaababb and aaababbb are all possible prefix of
    w with na (v) ≥ nb (v).
    4. Find context-free grammars for the language L = {an bm ck : k = |n − m|}. (with
    n ≥ 0, m ≥ 0, k ≥ 0)
    Answer.
    ∵ k = |n − m| ⇒ k = n − m for n ≥ m or k = m − n for m ≥ n, i.e., n = k + m or
    m = k + n.
    ∴ Parse L as L = L1 ∪ L2 , where L1 = {an bm ck : n = k + m} and L2 = {an bm ck :
    m = k + n}.
    A CFG for L1 is G1 = ({S1 , T1 , T2 }, {a, b, c}, S1 , P1 ) with production P1 as:
    S1 → T1 |T2
    T1 → aT1 b|λ
    T2 → aT2 c|T1 |λ
    A CFG for L2 is G2 = ({S2 , T3 , T4 }, {a, b, c}, S2 , P2 ) with production P2 as:
    S2 → T3 |T4
    T3 → aT3 b|λ
    T4 → bT4 c|λ
    Thus, a CFG for L is G = ({S, S1 , S2 , T1 , T2 , T3 , T4 }, {a, b, c}, S, P ) with production
    P as:
    S → S1 |S2
    S1 → T1 |T2
    T1 → aT1 b|λ
    T2 → aT2 c|T1 |λ
    S2 → T3 |T4
    T3 → aT3 b|λ
    T4 → bT4 c|λ
    2

    5. Show that the complement of the language L = {wwR : w ∈ {a, b}∗ } is context-free.
    Answer.
    A CFG for L is G = ({S}, {a, b}, S, P ) with production P as:
    S → a|b|ab|ba|aSa|aSb|bSa|bSb
    2

    1-2
    6. Consider the grammar with productions

    S → aaB,
    A → bBb|λ,
    B → Aa.

    Show that the string aabbabba is not in the language generated by this grammar.
    Answer.

    • 1st round: (1) S ⇒ aaB;


    • 2nd round: from (1), we have (2) S ⇒ aaB ⇒ aaAa;
    • 3rd round: from (2), we have (3) S ⇒ aaB ⇒ aaaa; (4) S ⇒ aaB ⇒ aaAaa;

    Thus, aabbabba cannot be generated by the given grammar. 2

    7. Construct an unambiguous grammar equivalent to the following grammar.

    S → AB|aaaB,
    A → a|Aa,
    B → b.

    Answer.
    This grammar produces the strings ab, aab, aaab, . . ., i.e., it generates G = ({S, A}, {a, b}, S, P )
    with productions.

    S → Ab,
    A → a|Aa.

    8. Give the derivation tree for (((a + b) ∗ c)) + a + b, using the grammar G = (V, T, E, P )
    with V = {E, T, F, I}, T = {a, b, c, +, ∗, (, )},

    E → T,
    T → F,
    F → I,
    E → E + T,
    T → T ∗ F,
    F → (E),
    I → a|b|c.

    Answer.
    2

    1-3
    9. Is the string aabbababb in the language generated by the grammar S → aaS|b?
    Answer.
    No. S → aaS|b cannot generate aabbababb.
    • 1st round: (1) S ⇒ aaS; (2) S ⇒ b;
    • 2nd round: from (1), S ⇒ aaS ⇒ aaaaS;
    Thus, we conclude that the string aabbababb cannot be generated by the given gram-
    mar. 2

    1-4

    You might also like