Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Hw03 Reglang Solution

    Uploaded by

    ankush ghosh
    This document contains solutions to homework problems about theory of computation including: 1) Corresponding regular expressions to language properties. 2) Determining if strings are in languages defined by regular expressions. 3) Finding minimum strings not in languages. 4) Writing regular expressions for specific languages. 5) Describing languages with regular expressions and set notation. 6) Combining languages using operations.

    Copyright:

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

    Hw03 Reglang Solution

    Uploaded by

    ankush ghosh
    61 views3 pages
    This document contains solutions to homework problems about theory of computation including: 1) Corresponding regular expressions to language properties. 2) Determining if strings are in languages defined by regular expressions. 3) Finding minimum strings not in languages. 4) Writing regular expressions for specific languages. 5) Describing languages with regular expressions and set notation. 6) Combining languages using operations.

    Original Description:

    numerical algorithms

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains solutions to homework problems about theory of computation including: 1) Corresponding regular expressions to language properties. 2) Determining if strings are in languages defined by regular expressions. 3) Finding minimum strings not in languages. 4) Writing regular expressions for specific languages. 5) Describing languages with regular expressions and set notation. 6) Combining languages using operations.

    Copyright:

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

    Hw03 Reglang Solution

    Uploaded by

    ankush ghosh
    This document contains solutions to homework problems about theory of computation including: 1) Corresponding regular expressions to language properties. 2) Determining if strings are in languages defined by regular expressions. 3) Finding minimum strings not in languages. 4) Writing regular expressions for specific languages. 5) Describing languages with regular expressions and set notation. 6) Combining languages using operations.

    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 3

    CmSc 365 Theory of Computation

    Homework 03 Solution

    1. Indicate the correspondence between the regular expressions to the left and the
    language properties to the right (the correspondence may be many-to-many, i.e. a
    language generated by a given regular expression may have several of the properties
    listed on the right side, as well as two or more expressions may generate languages
    having common properties).

    (a*b U a)ab 2, 3 1. Each string starts with a b


    b((ac)*a)* 1, 2 2. Each string contains no more than two b's
    (bc*a Ua*ba*) b 2, 5 3. Each string ends with ab
    bb*a U bab*ab* 1, 4 4. Each string contains ba as a substring
    a*(a*ba*b) 2, 5 5. Each string contains at least two b's

    2. True or False?

    a. abb L (a*b*a*b* ) True a1b2a0b0

    b. L (b*a*) L (a*b*) = L (a* b* ) True

    c. L (a*) L(b*) = False - the empty word is in the


    intersection

    d. ab L (a*) L(b*) False

    e. abab L (a*(aba*bb)*) False

    3. In each case, find a string of minimum length in {0, 1}* not in the language
    corresponding to the given regular expression

    a. 1*(01)*1* 0
    b. (0* U 1*)(0* U 1*)0 e
    c. 0*(101*)*0* 1
    d. 1*(0 U 01)*1* 0110

    4. Find a regular expression corresponding to each of the following subsets of {0,1}*:

    1
    Note: Below, for each language only one regular expression is given. However there
    may be other regular expressions that generate the same language.

    Example 1: The regular expression for the language that contains at least two
    occurrences of the substring 11 will be (0 U 1)*11(0 U 1)* 11(0 U 1)*
    First write what is required and then surround and insert in between all possible
    strings

    Example 2: The regular expression for the language that contains two types of strings:
    starting with one or more 1s and ending with zero or more 0s, and starting with one or
    more 0s and ending with zero or more 1s is
    11*0* U 00*1*

    a. The language of all strings containing exactly two 1s


    0*10*10*

    b. The language of all strings containing at least two 1s

    b1) (0 U 1)*10*1(0 U 1)*,

    b2) (0 U 1)* 1 (0 U 1)* 1 (0 U 1)*

    b2) generates the same strings as b1), b1) is shorter.

    c. The language of all strings that end with 01


    (0 U 1)* 01

    d. The language of all strings that begin with 11 and/or end with 00

    d1) 11(0 U 1)* U (0 U 1)*00

    d2) 11(0U1)* U (0U1)*00 U 11(0U1)*00

    d2) generates the same strings as d1) because 11(0U1)*00 is contained in


    11(0U1)* U (0U1)*00

    e. The language of all strings in which every 0 is followed immediately by 1

    e1) (1 U 01)*
    e2) 1*(011*)*
    e3) 1*(011*)*1*

    In e3) the last 1* is not necessary because the 1s at the end of a string can be
    generated by 1* in (011*)

    2
    f. The language of all strings containing 1111 as a substring
    (0 U 1)* 1111 (0 U 1)*

    5. Given and alphabet , the set of all possible strings over including the empty string
    is denoted by *.
    Let L = {a,b}* . The regular expression that describes all strings in L is (a U b)*

    Apply the above definitions to solve the following problems:

    a. The languages below are described as sets. Write the corresponding regular
    expressions for each of them

    L = {ab,ba}* (ab U ba)*


    L = {ayb: y {a,b}*} a(a U b)*b

    Note that (ab)* is different from a*b*

    b. For each regular expression below, give the set description of the
    corresponding language

    ab(a U b)* L = {abw | w {a,b}*}

    (a U ab)* L = {a, ab}*

    6. Given and alphabet , and two languages L1 , L2 *, L1 L2 is defined in the


    following way;

    L1 L2 = {xy : x L1 and y L2}

    a. Let L1= {hope, thought}, L2 = {less, ful}. Write down the elements of L1 L2.

    L1 L2. = {hopeless, hopeful, thoughtless, thoughtful}

    b. Let L1 be represented by the regular expression (a* U b*), and L2 be represented by


    ab. Write down the regular expressions that represent the following languages:

    L1 L2 (a* U b*)ab

    L1 L2 a* U b* U ab

    L1 L2

    You might also like