Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Mini

    Uploaded by

    aryansunilaryansunil15

    Copyright:

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

    Mini

    Uploaded by

    aryansunilaryansunil15
    4 views4 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Mini

    Uploaded by

    aryansunilaryansunil15

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    You are on page 1of 4

    Mini-Assignments

    Answer preparation - 03CS1003

    1. Write the regular expression for variable names. Assume that the variable name can
    start with alphabets or underscore and can also have digits but _____ is not a variable.
    (First 2 correct submissions accepted)

    The regular expression is :

    ( _ )* alphabet (alphabet | digit | _ )*

    2. Write the regular expression to represent an ip address. (First 5 correct submissions


    accepted)

    The regular expression for an ip will be

    (D)(.)(D)(.)(D)(.)(D)
    Where,
    D = (0|1|2|3|4|5|6|7|8|9) +
    (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) +
    (1)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) +
    (2)(0|1|2|3|4)(0|1|2|3|4|5|6|7|8|9) +
    (2)(5)(0|1|2|3|4|5)

    3. Given |r| the length of the regular expression, and |x| is the length of the input string
    write down the time and space complexity to test whether the string belongs to the
    regular expression or not by an (a) NFA and (b) DFA. (First 7 correct submissions
    accepted)

    NFA : Space complexity : O ( |r| )

    Time complexity : O ( |r| * |x| )

    DFA : Space complexity : O ( 2|r| )

    Time complexity : O ( |x| )


    4. Show the two trees produced by the grammar S-> aSbS | bSaS | epsilon. (First 10
    correct submissions accepted)

    the parse trees are

    S -> aSBS -> aebS -> ab(aSbS) -> ab(aebe) = abab


    and
    S -> aSbS -> a(bSaS)be -> a(beae)b = abab
    Where , e=epsilon

    5. Given the grammar


    E -> T E'
    E' -> + T E' | epsilon
    T -> F T'
    T' -> * F T' | epsilon
    F -> (exp) | id
    Construct for Recursive Predictive Parsing, minimum state transition diagram for the
    rules
    T -> F T'
    T' -> * F T' | epsilon
    (First 10 correct submissions accepted)

    The simplified finite automaton for T would be as follows :

    States={1,2,3}
    start state={1}
    final state={3}
    transition function :
    d(1,F)=2
    d(2,*)=1
    d(2,epsilon)=3

    However , we can implement the automaton by eliminating state 3 as


    well ,
    in which case state 2 will become the final state .
    States={1,2}
    start state={1}
    final state={2}
    transition function :
    d(1,F)=2
    d(2,*)=1
    6. Write down the CFG to detect the following. (a). occurence of balanced parentheses
    (b). strings over alphabet {a,b} such that every 'a' is followed by a 'b'. (First 10 correct
    submissions accepted)

    CFG for matched parenthesis :

    S -> (S) | SS | epsilon


    if epsilon is also considered a matching parenthesis

    else if epsilon is not considered a matching parenthesis ,


    S -> (A)
    A -> (A) | AA | epsilon

    CFG for the second problem where each 'a' must be followed by a 'b' :
    S -> Ab
    A -> a | Ab | Aba

    7. Given the grammar S -> iEtSS' | a


    S'-> eS
    E -> b.
    Prepare the first and follow list and the LL(1) parsing table. (First 20 correct submissions
    accepted)

    The CFG
    S  iEtSS’ | a
    S’ eS | ε
    Eb

    nullable FIRST FOLLOW


    Excluding ε
    S F i,a $,e

    S’ T e $,e

    E F b T

    Predictive parsing rules

    a b i e t $
    S Sa S iEtSS’

    S’ S’  eS S’  ε
    S’  ε

    E Eb

    8. Given the grammar


    S -> A
    A -> T | A + T | A - T
    T -> F | T * F | T / F
    F -> P | P ^ F
    P -> id | (A)
    Prepare the operator precedence table. (First 23 correct submissions accepted)

    $ ( ) Id ^ * / + -
    $ < < < < < < < <
    ( > < = < < < < < <
    ) > > > > > > > >
    Id > > > > > > > >
    ^ > < > < <
    * > < > < < > >
    / > < > < < > >
    + > < > < < < < > >
    - > < > < < < < > >

    Operator Precedence Table

    The precedence relations which have been left blank could not be determined by the
    specified rules .

    You might also like