Strings with the same number of a's before and after the first b in the string:
This language is context free, and not regular (it requires counting an
arbitrarily large number of a's, and is similar in format to parenthesis
matching). We can (and do) make the assumption that the string has at least
one b, and may have zero a's. This is not the only possible solution.
(S) ::= (Cs and Ds)(S)(Bs Cs and Ds)
(S) ::= a(S)a
(S) ::= b
(Cs and Ds) ::= c(Cs and Ds) | d(Cs and Ds) | epsilon
(Bs Cs and Ds) ::= b(Bs Cs and Ds) | c(Bs Cs and Ds) | d(Bs Cs and Ds) | epsilon
Strings where every b is immediately followed by an a:
This language is regular - the string can be analyzed character by character
with a finite number of states (did I just see a b or not?). We can (and I do)
assume that there can be no b's in a string in this language
Regular expression: (a+c+d+ba)*
Strings each c has the same number of a's before and after it.
The key to this language is to recognize that if each c has the same number of
a's before and after it, the c's must all be together, so we have a context
free language similar to the first one. I will assume that there may be no
a's and also no c's.
(S) ::= (Bs and Ds)(S)(Bs and Ds)
(S) ::= a(S)a
(S) ::= (Cs)
(Cs) ::= epsilon | c(Cs)| b(Cs)|d(Cs)
(Bs and Ds) ::= b(Bs and Ds) | d(Bs and Ds) | epsilon
(Note - slight change made since this went up, fixed error with bs/ds between cs. Oops. Note, this grammar is ambiguous.)
Palindrome - this is a stereotypical context free language
(S) ::= a|b|c|d|epsilon (base case)
(S) ::= a(S)a
(S) ::= b(S)b
(S) ::= c(S)c
(S) ::= d(S)d
Same number of letters palindrome - is not context free. We can not "remember" more than one piece of information with a context free grammar
Multiples of 7 - There's no predictable pattern to this, not context free.
Multiples of 16 - Regular. There must be 0s in the 1s, 2s, 4s, and 8s places.
Non-zero numbers start with a leading one, zero is also a multiple of 16.
Regular expression: 0 + 1(0+1)*0000
(translate to a/b if desired)
Please ask me in tutorial or in office hours if this material is still not familiar to you, but don't spend too much time on it - it should be a review, and I'd like you to start playing with Scheme.