Scribd Logo
Upload

Welcome to Scribd!

  • 68 views

    Tutorial 1 Discussion Document - Batch 03

    Uploaded by

    Anindya Costa
    1) The document provides examples of context-free grammars and the languages they generate. It also asks questions about defining languages using set notation and constructing grammars for regular expressions. 2) For questions about context-free grammars, the response uses set notation to precisely define the language generated by each grammar through derivations. 3) For regular expressions, grammars are constructed with nonterminals that generate the corresponding regular languages. Valid and invalid strings are used to illustrate the languages.

    Copyright:

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

    Tutorial 1 Discussion Document - Batch 03

    Uploaded by

    Anindya Costa
    68 views4 pages
    1) The document provides examples of context-free grammars and the languages they generate. It also asks questions about defining languages using set notation and constructing grammars for regular expressions. 2) For questions about context-free grammars, the response uses set notation to precisely define the language generated by each grammar through derivations. 3) For regular expressions, grammars are constructed with nonterminals that generate the corresponding regular languages. Valid and invalid strings are used to illustrate the languages.

    Original Description:

    DFSFES

    Original Title

    Tutorial 1 discussion document - batch 03

    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 examples of context-free grammars and the languages they generate. It also asks questions about defining languages using set notation and constructing grammars for regular expressions. 2) For questions about context-free grammars, the response uses set notation to precisely define the language generated by each grammar through derivations. 3) For regular expressions, grammars are constructed with nonterminals that generate the corresponding regular languages. Valid and invalid strings are used to illustrate the languages.

    Copyright:

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

    Tutorial 1 Discussion Document - Batch 03

    Uploaded by

    Anindya Costa
    1) The document provides examples of context-free grammars and the languages they generate. It also asks questions about defining languages using set notation and constructing grammars for regular expressions. 2) For questions about context-free grammars, the response uses set notation to precisely define the language generated by each grammar through derivations. 3) For regular expressions, grammars are constructed with nonterminals that generate the corresponding regular languages. Valid and invalid strings are used to illustrate the languages.

    Copyright:

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

    Tutorial 1 discussion – Batch 03

    Worked Example

    1) Use set notation to define the language of the grammar below:


    S → aS | aA | c
    A → Ab | λ
    L = {w ϵ {aic| i ≥ 0} U {ai bj | i ≥ 1; j ≥ 0}}
    S => c
    S => aS => ac
    S => aS => aaS => aac

    S => aA => a
    S => aS => aaA => aa
    S => aS => aaS => aaaA => aaa

    S => aA => aAb => ab


    S => aA => aAb => aAbb => abb
    S => aA => aAb => aAbb => aAbbb => abbb

    S => aA => aAb => ab


    S => aS => aaA => aaAb => aab
    S => aS => aaS => aaaA => aaaAb => aaab

    S => aA => aAb => ab


    S => aS => aaA => aaAb => aaAbb => aabb

    2) Construct a grammar over {a, b} that recognizes the language {aib2i | i ≥ 1}

    Example valid strings: abb, aabbbb, aaabbbbbb, etc.

    Invalid Strings: a, ab, aba…

    S → abb | aSbb

    S => abb

    S => aSbb => aabbbb

    S => aSbb => aaSbbbb => aaabbbbbb


    Questions:

    1) For each of the following grammars, use set notation to define the language generated by the
    grammar.
    a) S → aaSB | λ
    B → bB | b

    L = {w ϵ {a^2i b^i | i ≥ 1}}

    L = {w ϵ {a^2i b^j | i ≥ 0, j ≥ 0}}

    L = {w ϵ {a^2i b^j | i ≥ 1, j ≥ 1 }} U λ

    S => λ
    S => aaSB => aaB => aab
    S => aaSB => aaaaSBB => aaaaBB => aaaabB => aaaabb
    S => aaSB => aaB => aab
    S => aaSB => aaB => aabB => aabb

    2
    b) L = {w ϵ {a, b}* | w has odd length} //* can take a value 0 to ∞ In grammar, Upper case
    letters are called as non-
    Example valid strings: a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, ababa etc.. terminals. Meaning, they can
    be expanded.
    S → a | b | SSS
    Lower case letters are called
    S => a as terminals. Meaning, they
    S => b cannot be expanded. Always,
    S => SSS => aSS => aaS => aaa alphabets will be terminals.
    S => SSS => SSSSS
    Left most derivation or right most derivation.

    S → a | aA | b | bA
    A → aS |bS
    S => a
    S => aA => aaS => aaa
    S => aA => aaS => aaaA => aaaaS => aaaaa
    S => b
    S => bA => bbS => bbb
    S = aA => abS => aba

    c) {w ϵ {a, b}* | w has b’s followed by a’s}

    e.g., strings are: ba, bbaa, baa, bbbbaaaaaaaaaaaaaaa


    e.g., invalid strings: ab, bab, baba
    The above grammar is right and it is one possible answer.

    e) L = {w ϵ {a, b} |w is {anbn | n ≥ 0}}


    e.g., e, ab, aabb, aaabbb and so on…
    abab

    S → λ | ab | aSb
    S => aSb => aaSbb => aaabbb
    S => aSb => ab
    S => ab

    S → λ | aSb

    S => aSb => ab


    S => aSb => aaSbb => aabb

    3. For each of the following Regular Expressions, write a regular grammar that defines the same
    language.

    b) L = (a υ b υ c)* a(a υ b υ c)* b(a υ b υ c)* υ (a υ b υ c)* b(a υ b υ c)* a(a υ b υ c)*

    a b U ba

    (a υ b υ c)*
    w = e, a, b, c, aa, ab, ac, bb, cc, bc, cb, ca, ba, aaa, abc, cba, bac, cab, bbb, etc.

    A = (a υ b υ c)*

    S → AaAbA | AbAaA
    A → e | aA | bA | cA

    A => aA => a
    A => aA => aaA => aa
    A => bA => baA => bacA => bac
    c) a(a υ b υ c)* b(a υ b υ c)*

    S → aAbA
    A → λ | aA | bA | cA

    You might also like