CS385, Fall 2010
Theory of Computation
Problem Set 6 Solutions

  1. Find a concise formal symbolic description of the language that is generated by the context-free grammar below. Explain.
    S → aSc | Sc | aTc
    T → aaTb | aTb | Tb | aab | ab | b
    A formal symbolic description should specify the string patterns that are allowed in the target language. It should not involve any recursion or undefined variables, and should clearly determine, for a given string, whether the string belongs to the target language or not. An example of the sort of answer that is required is:
    L = { a2n bm | n ≥ 3m and m ≥ 1 }

    Solution

    L = { an bm cp | n ≤ 2m + p; n,m,p ≥ 1}
    Here's why. Any derivation in the given grammar begins with zero or more applications of the recursive cases of the S-rule, followed by a single application of the rule S → aTc, followed by recursion in the T-rule, and ends with a single application of one of the "base case" T-rules T → aab | ab | b. We'll follow this general derivation, keeping track of the partially generated string at each point.

    Application of the two recursive cases of the S-rule a total of j times yields the string ai S cj, where i is the number out of the j applications in which the subrule S → Sc was applied; therefore, we have the constraint 0 ≤ i ≤ j and j ≥ 0 but no other constraints. Application of the rule S → aTc now yields the string ai+1 T cj+1, or, equivalently, after renaming, ai T cj, where 1 ≤ i ≤ j.

    Recursion in the T-rules exactly t times yields ai+s T bt cj, where 0 ≤ s ≤ 2t and t ≥ 0 (the value of s depends on exactly how many times each of the specific recursive T-rules is applied: s = 2x + y, where x is the number of applications of the subrule T → 00T1 and y is the number of applications of the subrule T → 0T1).

    Finally, one of the base case rules is applied to finish the derivation. This produces the terminal string ai+s bt+1 cj, in which 1 ≤ i ≤ j, s ≤ 2t, and t ≥ 0. Equivalently, relabeling the b exponent: ai+s bt cj, where 1 ≤ i ≤ j, s ≤ 2t, and t ≥ 1. Combining the constraints on the summands in teh a exponent and relabeling: ai bt cj, where 1 ≤ i ≤ j+2t, j ≥ 1, and t ≥ 1. This proves that the language generated by the given grammar satisfies the claimed formal symbolic description.

  2. Design a context-free grammar that generates the language of strings over the alphabet 0,1,2 of the form 0a 1b 2c, where b ≥ 2a + 3c, and each of a, b, c is ≥ 0. Use exactly three variables named S, A, Z in your grammar. Explain the rationale behind your design. In particular, state precisely what sequence of applications of the rules in your grammar will generate a generic string 0a 1b 2c of the target language. Suggestion: use variable A to generate 0,1 pairings and variable Z to generate 1,2 pairings together with any additional 1's.

    Solution

    Following my own suggestion:

    S -> AZ
    A -> 0A11 | ε
    Z -> 111Z2 | 1Z | ε

    In order to derive any string of the form 0a 1b 2c, where b ≥ 2a + 3c, and each of a, b, c is ≥ 0:

    Begin by applying the rule S -> AZ, of course.

    Next, apply the rule A -> 0A11 exactly a times, yielding the string 0a A 12a Z.

    Apply the rule A -> ε to eliminate A, yielding the string 0a 12a Z.

    Now the "Z mode" takes over. Apply the rule Z -> 111Z2 exactly c times, yielding the string 0a 12a+3c Z 2c.

    Apply the rule Z -> 1Z exactly b - (2a+3c) times, yielding the string 0a 1b Z 2c.

    Finally, eliminate the Z using the rule Z -> ε to obtain the desired string.

  3. a) Construct an NFA that recognizes the language of strings over the numerical alphabet 0-9 that represent valid positive integers of the form 3n + 1 in standard decimal positional notation. Examples include 4, 10, 301, 907. Leading 0's are not allowed.

    Solution

    We use states that represent the three different possible remainders modulo 3, and accept only if the net remainder is 2. An extra state is required in order not to allow leading 0's as required by the above statement. 
            state space Q = {start, zero, one, two}

        transition function:

                start --> zero on inputs 3, 6, 9
                start --> one on inputs 1, 4, 7
                start --> two on inputs 2, 5, 8
                (notice: no 0-transition leaving the start state)

                zero --> zero on inputs 0, 3, 6, 9
                zero --> one on inputs 1, 4, 7
                zero --> two on inputs 2, 5, 8

                one --> one on inputs 0, 3, 6, 9
                one --> two on inputs 1, 4, 7
                one --> zero on inputs 2, 5, 8

                two --> two on inputs 0, 3, 6, 9
                two --> zero on inputs 1, 4, 7
                two --> one on inputs 2, 5, 8

        set of accept states = {one}

    b) Use the procedure described in class to transform your NFA from part a) into a context-free grammar that generates the given language. Provide each of the four ingredients that are required in the formal definition of the grammar. Explain how each ingredient of your grammar is constructed in terms of specific features of your NFA from part a). Name the variables in your grammar exactly the same as the corresponding states in your NFA.

    Solution

            set of variables V = {start, zero, one, two}

        terminal alphabet = {0-9}

        production rules:

                start --> 3zero | 6zero | 9zero
                start --> 1one | 4one | 7one
                start --> 2two | 5two | 8two

                zero --> 0zero | 3zero | 6zero | 9zero
                zero --> 1one | 4one | 7one
                zero --> 2two | 5two | 8two

                one --> 0one | 3one | 6one | 9one
                one --> 1two | 4two | 7two
                one --> 2zero | 5zero | 8zero

                two --> 0two | 3two | 6two | 9two
                two --> 1zero | 4zero | 7zero
                two --> 2one | 5one | 8one

                one --> epsilon      (since one is an accepting state)

        start symbol = {start}

  4. Design a PDA that recognizes the language below. Explain.
    L = { an bm cp | 1 ≤ p ≤ 2n + 3m }

    Solution

    Here's an informal verbal description of the operation of a PDA that recognizes the given language. Extracting a state diagram and/or formal definition is straightforward (exercise, and we can discuss in class). Use four states S, A, B, C, where S is the start state and C is the only accepting state. S has a self-transition on input a, in which aa is pushed onto the stack (in a standard PDA, this should be done using two distinct states, and two transitions, each of which pushes a single a). There is an epsilon transition from S to A (no stack operations, either). A has a self-transition on input b, which pushes aaa onto the stack (again, use three states and three single push moves in a standard PDA). There is an epsilon transition from A to B (no stack operations, either). B has a self-transition on input c, which pops an a. There is a transition from B to C on input c, which pops an a. C has a self-transition on input epsilon, which pops an a.