Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    Assignment 3

    Uploaded by

    Sujan Thapaliya
    This document contains 34 questions about regular expressions, finite automata, and regular languages. It asks the reader to write regular expressions for certain languages, convert between regular expressions, finite automata, and regular languages, prove languages are or aren't regular using the pumping lemma, and demonstrate closure properties and conversions between different representations of regular languages. It focuses on testing understanding of core concepts in the theory of computation regarding regular languages and regular expressions.

    Copyright:

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

    Assignment 3

    Uploaded by

    Sujan Thapaliya
    22 views3 pages
    This document contains 34 questions about regular expressions, finite automata, and regular languages. It asks the reader to write regular expressions for certain languages, convert between regular expressions, finite automata, and regular languages, prove languages are or aren't regular using the pumping lemma, and demonstrate closure properties and conversions between different representations of regular languages. It focuses on testing understanding of core concepts in the theory of computation regarding regular languages and regular expressions.

    Original Description:

    assessment

    Original Title

    Assignment-3

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains 34 questions about regular expressions, finite automata, and regular languages. It asks the reader to write regular expressions for certain languages, convert between regular expressions, finite automata, and regular languages, prove languages are or aren't regular using the pumping lemma, and demonstrate closure properties and conversions between different representations of regular languages. It focuses on testing understanding of core concepts in the theory of computation regarding regular languages and regular expressions.

    Copyright:

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

    Assignment 3

    Uploaded by

    Sujan Thapaliya
    This document contains 34 questions about regular expressions, finite automata, and regular languages. It asks the reader to write regular expressions for certain languages, convert between regular expressions, finite automata, and regular languages, prove languages are or aren't regular using the pumping lemma, and demonstrate closure properties and conversions between different representations of regular languages. It focuses on testing understanding of core concepts in the theory of computation regarding regular languages and regular expressions.

    Copyright:

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

    Theory of Computation

    By: Assistant Professor Loknath Regmi


    Assignment -3
    Regular Expressions
    1. Write the regular expression over {0, 1} for following strings
    a.
    b.
    c.
    d.
    e.
    f.
    g.
    2. Describe in words the strings in each of these regular sets
    a. 1*0
    b. 1*00*
    c. 0(1+0)*
    d. (0+1)(0+1)*00
    3. Write regular expressions that accepts the dates of the format
    - 12/31/2008
    - December 31, 2008
    - Wednesday, December 31, 2008
    4. Write regular expressions that validate
    a. A website url
    b. An email address
    c. An IPV4 address
    d. A MAC address
    e. A Zip Code
    5. Configure equivalent epsilon NFA for following regular expressions
    a. (((00)*(11)*))U01)*
    b. *
    c. (ab U a)*
    6. Convert following Finite Automata to equivalent regular expressions;
    7. Minimize the following DFAs using the table filling algorithm.

    8. Minimize the following DFA:

    9. Define finite Automata with e-moves. NFA has more computation power than DFA?
    Explain.
    10. Give the regular expression for the following languages.
    a. L= {SS {a, b}* and S starts with aa or b and does not contains
    substring bb.
    b. L= {S |S { 0, 1}* and 0 occurs in pairs if any and ends with 1.
    11. How a ∈-NFA can be converted into NFA and DFA? Explain with a suitable example.
    12. Find the minimum state DFA equivalent to the following DFA.

    State 0 1
    B C

    B B D
    C E D
    D E D
    *E A D
    13. Show that a language L is accepted by some NFA if and only if it is accepted by some
    DFA. Or Show that a language L is accepted by some DFA if and only if L is accepted
    by some NFA.
    14. Give the regular expression for the following languages.
    a. and S starts with aa or b and does not contains substring bb .
    b. and 0 occurs in pairs if any and ends with 1.
    15. For a regular expression (a+b)*baa, construct ε-NFA.
    16. State and prove pumping lemma for regular language. Show by example how it can be
    used to prove a language is not a regular.
    17. Show that language of palindrome over {a,b} is not a regular language.
    18. Show that for any regular expression, there is a NFA that accepts the same language
    represented by r. Convert the regular expression (a+b) (aa+ba)* + ab(a+b)* bba into
    NFA.
    19. What do you mean by regular expressions? Explain with example of pumping lemma
    for regular languages.
    20. What do you mean by pumping lemma for regular languages?
    21. Draw NFA corresponding to following regular expression over ∑ = {0,1}
    010* + 0(01+10)* 11
    22. For the following regular expression draw an NFA - ^ recognizing the corresponding
    languages.
    i) (00 +1)*(10)*
    ii) 001*0*11
    23. Prove that any regular language can be accepted by a finite automata with all details.
    24. What are the regular operators applied to the regular languages? Explain with example.
    25. Simplify the following regular expressions.
    a.) 1*+1*0(ɛ+0+1)*ø
    b.) ɛ+0+1+( ɛ+0+1)( ɛ+0+1)*( ɛ+0+1)
    26. State the pumping lemma for regular language. Show by example, how can you use it to
    prove that a language is not regular.
    27. What are the algebraic rules for regular expressions? Also show that if L, M, N are any
    regular language then show that L(M U N) = L.M U L.N.
    28. Write regular expressions for the following regular languages.

    a) The set of strings over alphabet {a, b} containing at least one 'a' and at least
    one 'b'.
    b) The set of strings over {0, 1} whose 5th symbol from right end is 1.

    29. Convert the following regular expression into -NFA.


    a) 01* b) (0 + 1)01* c) 00 + (0 + 1) *100*

    30. Prove that the language is not regular.


    31. Prove that the language is not regular.
    32. Prove that the language is not regular.
    33. Prove that the language is not regular.
    34. Prove that the language is not regular.
    35. Find the regular expression for the language has 0101 as substring.
    36. Construct a NFA for the language (ab*a U b*aa). Provide any two accepted strings and
    two rejected string.
    37. Define Closure properties of Regular Language' Prove that regular Language under
    Union, Intersection and Complementation operation.
    38. List closure properties of regular language. If M and N are any two regular languages
    then show that L: (MUN) is also regular language.

    You might also like