Homework 20 Unrestricted Grammars 1 CS 341 Homework 20 Unrestricted Grammars 1. Find grammars that generate the following languages: (a) L = {ww : w ∈ {a, b}*} (b) L = {an2 : n ≥ 0} (c) L = { anb2nc3n : n ≥ 1} (d) L = {wR : w is the social security number of a living American citizen} (e) L = {wcmdn : w ∈ {a, b}* and m = the number of a's in w and n equals the number of b's in w} 2. Find a grammar that computes the function f(w) = ww, where w ∈ {a, b}*. Solutions 1. (a) L = {ww : w ∈ {a, b}*} There isn’t any way to generate the two w’s in the correct order. Suppose we try. Then we could get aSa. Suppose we want b next. Then we need Sa to become bSab, since the new b has to come after the a that’s already there. That could work. Now we have abSab. Let’s say we want a next. Now Sab has to become aSaba. The problem is that, as the length of the string grows, so does the number of rules we’ll need to cope with all the patterns we could have to replace. In a finite number of rules, we can’t deal with replacing S (which we need to do to get the next character in the first occurrence of w), and adding a new character that is arbitrarily far away from S. The other approach we could try would be have a rule S → WW, and then let W generate a string of a's and b's. But this won't work, since we have no way to control the expansion of the two W's so that they produce the same thing. So what we need to do is to generate wwR and then, carefully, reverse the order of the characters in wR. What we’ll do is to start by erecting a wall (#) at the right end of the string. Then we’ll generate wwR. Then, in a second phase, we’ll take the characters in the second w and, one at a time, starting with the leftmost, move it right and then move it past the wall. At each step, we move each character up to the wall and then just over it, but we don’t reverse characters once they get over the wall. The first part of the grammar, which will generate wTwR, looks like this: S → S1 # This inserts the wall at the right. S1 → aS1a S1 → bS1b S1 → T T will mark the left edge of the portion that needs to be reversed. At this point, we can generate strings such as abbbTbbba#. What we need to do now is to reverse the string of a’s and b’s that is between T and #. To do that, we let T spin off a marker Q, which we can pass rightward through the string. As it moves to the right, it will take the first a or b it finds with it. It does this by swapping the character it is carrying (the one just to the right of it) with the next one to the right. It also moves itself one square to the right. The four rules marked with * accomplish this. When Q’s character gets to the # (the rules marked **), the a or b will swap places with the # (thus hopping the fence) and the Q will go away. We can keep doing this until all the a’s and b’s are behind the fence and in the right order. Then the final T# will drop out. Here are the rules for this phase:Homework 20 Unrestricted Grammars 2 T → TQ Qaa → aQa * Qab → bQa * Qbb → bQb * Qba → aQb * Qa# → #a ** Qb# → #b ** T# → ε So with R as given above, the grammar G = ({S, S1, #, T, Q, a, b}, {a, b}, R, S} (b) L = {an2 : n ≥ 0} The idea here is first to generate the first string, which is just a. Then think about the next one. You can derive it by taking the previous one, and, for every a, write two a’s. So we get aa. Now to get the third one, we do the same thing. Each of the two a’s becomes two and we have four, and so forth. So we need a rule to get us started and to indicate the possibility of duplication. Then we need rules to actually do the duplication. To make duplication happen, we need a symbol that gets generated by S indicating the option to repeat. We’ll use P. Since duplication can happen an arbitrary number of times, we need P to spin off as many individual duplication commands as we want. We’ll use R for that. The one other thing we need is to make sure, if we start a duplication step, that we finish it. In other words, suppose we currently have aaaa. If we start duplicating the a’s, we must duplicate all of them. Otherwise, we might end up with, for example, seven a’s. So we’ll introduce a left edge marker, #. Once we fire up a duplication (by creating an R), we’ll only stop (i.e., get rid of R) when R has made it all the way to the other end of the string (namely the left end since it starts at the right). So we get the following rules: S → #aP P lets us start up duplication processes as often as we like. P → ε When we’ve done as many as we want, we get rid of P. P → RP R will actually do a duplication by moving leftward, duplicating every a it sees. aR → Raa Actually duplicates one a, and moves R one square to the left so it moves on to the next a #R → # Get rid of R once it's made it all the way to the left # → ε Get of # at the end So with R as given above, the grammar G = ({S, P, R, #, a, b}, {a, b}, R, S} (c) L = { anb2nc3n : n ≥ 1} This one is very similar to anbncn. The only difference is that we will churn out b's in pairs and c's in triples each time we expand S. So we get: S → aBSccc S → aBccc Ba → aB Bc → bbc Bb → bbb So with R as given above, the grammar G = ({S, B, a, b, c}, {a, b, c}, R, S} (d) L = {wR : w is the social security number of a living American citizen} This one is regular. There is a finite number of such social security numbers. So we need one rule for each number. Each rule is of the form S → <valid number>. So with that collection of rules as R, the grammar G = ({S, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 1, 2, 3, 4, …
View Full Document
Unlocking...