Scribd Logo
Upload

Welcome to Scribd!

  • 509 views

    ASG - Ans

    Uploaded by

    rmidhunajyothi
    The document contains instructions for several teams to complete tasks involving finite automata (FA) and regular expressions. The tasks include constructing deterministic finite automata (DFAs) for various languages, converting nondeterministic finite automata (NFAs) to equivalent DFAs, writing regular expressions for languages, and minimizing automata. Solutions are provided for some tasks.

    Copyright:

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

    ASG - Ans

    Uploaded by

    rmidhunajyothi
    509 views17 pages
    The document contains instructions for several teams to complete tasks involving finite automata (FA) and regular expressions. The tasks include constructing deterministic finite automata (DFAs) for various languages, converting nondeterministic finite automata (NFAs) to equivalent DFAs, writing regular expressions for languages, and minimizing automata. Solutions are provided for some tasks.

    Original Description:

    TOC Assignment

    Original Title

    ASG -Ans.doc

    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?

    The document contains instructions for several teams to complete tasks involving finite automata (FA) and regular expressions. The tasks include constructing deterministic finite automata (DFAs) for various languages, converting nondeterministic finite automata (NFAs) to equivalent DFAs, writing regular expressions for languages, and minimizing automata. Solutions are provided for some tasks.

    Copyright:

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

    ASG - Ans

    Uploaded by

    rmidhunajyothi
    The document contains instructions for several teams to complete tasks involving finite automata (FA) and regular expressions. The tasks include constructing deterministic finite automata (DFAs) for various languages, converting nondeterministic finite automata (NFAs) to equivalent DFAs, writing regular expressions for languages, and minimizing automata. Solutions are provided for some tasks.

    Copyright:

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

    TEAM 1 Construct a DFA that shall recognize the language L={ bmabn | m,n > 0}

    1.1

    Soln 1.1: Construct the minimum state automata equivalent to the given FA
    1.2

    Soln 1.2: 1.3 Convert the following NFA to DFA

    Soln 1.3:

    1.4 Write a regular expression for the set of all strings which have an even no: of 0s or an even no: of 1s.

    1.5 Construct DFA to accept 00(0+1)*

    TEAM 2 2.1 Determine the DFA that will accept those words from = {a,b} where the no: of bs is divisible by 3.

    2.2 Convert the following NFA to DFA

    Soln:

    2.3 Write a regular expression for the set of all strings with alternate 0s and 1s. ( + 1)(01)* ( + 0) 2. 4 Construct the minimum state automata equivalent to the given FA

    Soln:

    2.5 Design DFA to accept 00(0+1)*11

    TEAM 3 3.1 Determine the FA if ={a,b} for L= {(ab)n|n0}

    Soln:

    3.2 Obtain the regular expression for the language:


    a)

    L1= { a2n b2m+1|n,m0} (aa)*(bb)*b

    b)

    L2= { am bm|m>0} aa*bb* or a*ab*b

    3.3 Construct the minimum state automata equivalent to the given FA

    Soln:

    3.4 Convert the given NFA to DFA

    3.5 Design DFA to accept 00(0+1)*

    TEAM 4 4.1 Construct the minimum state automata equivalent to the given FA

    Soln:

    4.2 Determine the FA if ={a,b} for L= {(ab)n|n1} Soln:

    4.3 Convert the following NFA to DFA

    4.4 Construct an NFA equivalent to the regular expression (0+1) (00+11) (0+1)

    TEAM 5 5.1 Minimize the following automaton

    5.2 Construct the DFA where L = {x {a,b}* | x ends with b and doesnot contain the substring aa} Soln:

    5.3 Write a regular expression for the set of all strings with an even no: of as followed by an odd no: of bs. Write the language also. (aa)*(bb)*b L= {a2n b2m+1 : n0,m 0} 5.4 Convert the given NFA to DFA

    5.5

    TEAM 6 6.1 Design a DFA in which every a is preceded by b

    6.2 Construct the minimum state automata equivalent to the given FA

    6.3 Convert the given NFA into equivalent DFA

    TEAM 7 7.1 Design a FSM to accept those strings having 101 or 110 as substring.

    7.2 Minimize the following automaton

    7.3 Design DFA to accept (0+1)*11

    7.4 Convert NFA to DFA

    TEAM 8 8.1 Design a DFA which accepts a binary no: which is odd.

    8.2 Minimize the following automaton

    8.3 Convert NFA to DFA

    TEAM 9 9.1Construct a DFA for { w | w {0,1}* , w contains the substring


    1010} Soln:

    9.2 Write the regular expression for the language L={w {0,1}* : w has no pair of consecutive zeroes} (1+01)*(0+)

    9.3 Minimize the following automaton

    9.4 Convert NFA to DFA

    TEAM 10 10.1 Construct a DFA such that {w|w begins with 01 and ends with 01}

    10.2 Convert NFA to DFA

    TEAM 11 11.1.a Construct a DFA such that {w|w contains the substring 110}

    11.1.b Construct a DFA such that {w|w does not contain the substring 110}

    11.2 Minimize the following automaton

    11.3 Convert NFA to DFA

    You might also like