Lanuage grammar help

Ok, I'm having some trouble understanding language grammar. I've been trying to figure out these couple exercises, but I need some help.

The first asks to find all possible strings of seven or fewer letters using this language:

Code:

---

<string>=$ | <word> | $<string>
<word>=abb | a<word>bb

---

Where | means "or".

This is what I have so far:

Code:

---

$
abb
aabbbb
$$
$$$
$$$$
$$$$$
$$$$$$
$$$$$$$
$abb
$aabbbbb

---

I feel like I'm missing something.

The other was about writing recursive grammar for a language of strings of one or more letters. The first letter must be uppercase, and the other letters must be lowercase.

Here is what I got:

Code:

---

<string>=<upper> | <string><lower>
<upper>=A | B | ...Z
<lower>=a | b | ...z

---

Can someone confirm if I'm doing it right?

Thanks a lot for any input! :D

Both your answers look correct to me.

Can you not do $$abb (etc)?

Quote:

---

Originally Posted by tabstop

Can you not do $$abb (etc)?

---

To an extent, I believe... if I'm reading it right.

According to the rules

Code:

---

<string>=$ | <word> | $<string>
<word>=abb | a<word>bb

---

<string> can equal <word> ("abb" or "aabbbb") and as such, according to the third conditional value of <string> can also equal $<word> (where <string> in the condition is substituted for it's second conditional value <word>),
recursively to 7 letters. That would add the possibilities of:

Code:

---

* Text left hidden for OP, if he still wishes to figure them out
$abb
$$abb
$$$abb
$$$$abb
$aabbbb

---

Of course... it is 1AM.

The valid forms of the first grammar are:
"$" (from the '$' term of the <string> rule)
any combination of n times 'a' followed by 2n times 'b', where n > 0 (the <word> rule and term)
either of the above, prefixed by any number of '$' characters. (repeated application of the $<string> term)

The second is correct.

Note that $aabbbbb has eight letters and hence doesn't belong to your list.

The grammar above is a so-called context-free grammar, or Type-2 grammar in the Chomsky hierarchy. This hierarchy lets you easily determine what can be expressed in a certain grammar and how much effort is needed to decide whether a given word belongs to the corresponding language or not. My literature on this subject is in German, but I'm sure that there are plenty of books available in English as well.

Greets,
Philip

Quote:

---

Originally Posted by Snafuist

Note that $aabbbbb has eight letters and hence doesn't belong to your list.

---

It's also not valid under the grammar. Looks like a typo.