1. More Grammar Problems

Here are some grammar problems that I can't seem to wrap my brain around. I've already solved them but I want to see what you guys think:

5. (2 points) Write a grammar that describes the following language:

6. (2 points) consider the following grammar:
S X Y X x
Y Y y
Y y

This grammar describes a language (i.e. a set of strings). Describe (in simple English) the set of strings that this grammar describes.
7. (3 points) Optional extra credit question: Given the alphabet {a, b} write a grammar for the following language:

8. (3 points) Optional extra credit question 2: What language does the following grammar define? Describe it in simple English.
S aZ b Z aZ b Z ab

2. Re: More Grammar Problems

5.

1. S → A
2. A→ ac
4. C → ab

6.
1. The S is replaced with XY (by rule 1). So then we’re left with XY.
2. The X in XY turns into x by rule 2.
3. The Y in XY becomes Yy by rule 3.
4. The Y in Yy is replaced with y by rule 4 which leaves us with yy. So now we have xyy

7.

1. S → AB
2. A→ Aa
3. A → a
4. B → b
5. B → ab

8.
1. The S is replaced with aZb (by rule 1) which leaves us with aZb.
2. The Z in aZb is replaced with aZb by rule 2. This leaves us with aZb.
3. The Z in aZb is replaced with ab (by rule 3). This leaves us with aabb.

3. Re: More Grammar Problems

5 will never generate B or C. I'd try:
$S\to AB$
$A\to a$
$B\to b$
$B\to c$
$B\to d$

6. By the rules you have shown in other problems, I do not believe they are activated in order.
S becomes XY is true. X becomes x is true, but I believe either Y becomes Yy OR Y becomes y. This would mean that you can get xy, xyy, xyyy, etc. It is x followed by a finite number of y's (I say finite because most languages require strings to be finite)

4. Re: More Grammar Problems

7 is also wrong. You cannot get the following string: abaa.

5. Re: More Grammar Problems

8 again seems to imply an or, not a strict adherence to the order in which the rules were listed. You can wind up with a string of a's concatenated with an equally sized string of b's where you have at least 2 of each.

6. Re: More Grammar Problems

I re-did #7 and this is what I got. The only thing I am certain is that this is for grammar-free problems. Nevertheless I gave a second shot.

1. S → AB
2. A→ Aa
3. A → a
4. B → b
5. B → ab
6. B → ε
7. A → ε

7. Re: More Grammar Problems

What does $\varepsilon$ mean? Is that the null string?

8. Re: More Grammar Problems

Yes. It means it's emty.

9. Re: More Grammar Problems

$S \to AB$
$A \to a$
$B \to aB$
$B \to bB$
$B \to \varepsilon$

Now, it starts with an a. The next character could be a or b or nothing, followed by a or b or nothing, followed by a or b or nothing...

10. Re: More Grammar Problems

Doesn't b need to be alone at some point? Or does that violate the language ("The language that has/accepts all strings that start with an a”) given?

11. Re: More Grammar Problems

Originally Posted by marsandfruit
Doesn't b need to be alone at some point? Or does that violate the language ("The language that has/accepts all strings that start with an a”) given?
I don't believe that is necessary. You could have $b$ alone if you want to. But, essentially, what my rules state is that it must begin with an a. Then, it has three choices. It can add an $a$ + keep going, it can add a $b$ + keep going, or it can stop. So, after the first pass, it will be one of these:
aaB
abB
a

If it goes for two passes, here are the six choices:
aaaB
aabB
aa
abaB
abbB
ab

If it goes for three passes, it would be one of these twelve:
aaaaB
aaabB
aaa
aabaB
aabbB
aab
abaaB
ababB
aba
abbaB
abbbB
abb

You see how each step, it adds another character and keeps going or it stops?

12. Re: More Grammar Problems

Originally Posted by marsandfruit
Doesn't b need to be alone at some point? Or does that violate the language ("The language that has/accepts all strings that start with an a”) given?
Nevermind. I understand why now. Sorry I'm just learning this stuff and I want to make sure it's correct.

13. Re: More Grammar Problems

Yes I do! Thank you so much!

And for #8 would there be a similar statement to define the language? Would be "Anything after a is included in this language."

14. Re: More Grammar Problems

You can wind up with:
aabb
aaabbb
aaaabbbb
aaaaabbbbb

It is a number of a's (at least two) followed by an equal number of b's

This is certainly not anything after a.