Strings from grammar

Question

I must have dozed off in class. I have an exam tommorow and this is on the review sheet and i have no idea what this means. If someone could explain it and/or have a link for somewhere I can learn about "it" that would be helpful. thanks

Consider the language that the following grammar defines:

< S > ::= $ | < W > | $< S >

< W > ::= abb | a < W > bb

Write all strings that are in this language and contain seven or fewer character

Edit: Heres another example:

< Str >::= X< Str > | Y< Another > < Another >::= Z | Z< Another >

Write some string in this language that contains more than three characters.

Answer 1

Looks like you slept through the class on Backus–Naur Form.

The first example has two rules.

The first:

< S > ::= $ | < W > | $< S >

Says that <S> is either a dollar symbol, a <W> or a dollar followed by a <S>

The second:

< W > ::= abb | a < W > bb

Says that <W> can be abb or can be a followed by a <W> followed by bb

Notice that in this example, an <S> can contain another <S> and a <W> can contain another <W>

So the list of all the strings that are less than 8 characters would start:

$
$$
$$$
$$$$
$$$$$
$$$$$$
$$$$$$$

And that's before we have even considered using the rule for <W>.

Lets hope the questions in your exam are more like the second example. The answer for which could be as simple as XYZZ