So I was going through the course archives for our CS program and looked at some notes and quizzes from a class that was last taught in Spring of 2008 that I will be taking Fall of 2009. It's called Survey of Programming Languages and I found the section on grammar to be interesting.

Here are the questions I'm referencing:



# Consider the regular expression a((ab)*|(ba)*)b.

1. Which one of the following strings is not accepted by this regular expression?
* ab
* aababb
* ababb
* abababab
2. Which one of the following strings is accepted by this regular expression?
* bababb
* aababb
* aabababa
* abaabb

# Consider this grammar in BNF.

<S> -> a<B> | b<A>
<A> -> a | a<S> | b<A><A>
<B> -> b | b<S> | a<B><B>

Show that the string baab is in the language by providing a derivation.

Consider the following grammar:

<S> --> <A>
<A> --> <A> + <A> | <id>
<id> --> a | b | c

Give an example of an ambiguous sentence in this language.
Give an example of something that is bound at language design time.
Give an example of something that is bound at language implementation time.
Give an example of something that is bound at compile time.
Give an example of something that is bound at load time.
Give an example of something that is bound at run time.

I suppose I'm lost because whoever that professor was didn't upload the presentations (forcing students to come to class), but if you guys know what this stuff means and can point me in the right direction I'd really appreciate it!

I can at least look at this reference,
Basically the regex can be broken down as such
1. look for an a
2. now look for either none or more ba,
OR
none or more ab
(But not both)
3. look for a b at the end.

Thus the first question #1 would fail on this line : ababb
because you have ababb and since there is no a after the second b it fails a "change" that would make this work would be:
ababab

For question #2 can you apply the same concept as the steps above and determine which will fail
(should be pretty easy to cut it down to 2 and from there just look closely)

Good luck and as far as the rest of your question I have no clue...sorry.