languages of grammar examples

Example 1:
S ? aSbS | bSaS | ?
Leftmost Derivation for aabb:

S ? aSbS
? aaSbSbS
?aabSbS
? aabbS
?aabb
Rightmost Derivation:
S ?aSbS
?aSb
?aaSbSb
?aaSbb
?aabb


Example 2:
Find L(G) where G = ({S, S1, S2}, {a, b}, S, P) with

S ? S1ab,
S1?S1ab | S2,
S2 ? a.

Answer. This is a left-linear grammar.

S ? S1ab ? S1abab ? S2abab ?aabab.
Then
L(G) = {aabw |w ? (ab)*}.

L = {w ? {a, b, c}+ : number of a s, b s and c s is the same}
S ? ABCS
S ? ABC
AB ? BA
BC ? CB
AC ? CA
BA ? AB
CA ? AC
CB ? BC
A ? a
B ? b
C ? c

Example 4: The following grammar is context-sensitive.
S ? aTb | ab
aT ? aaTb | ac.
What is the language of the grammar?
{ab} U {a n+1cb n+1 | n ? 0}.
This language is context-free, it has the grammar
S ? aTb | ab, and T ? aTb | c. Any context-free language is context sensitive.

Example 1: Let G1 = ({0, 1}, {S, T,O, I}, S, P), where P contains the following productions:
S ? OT
S ? OI
T ? SI
O?0
I ? 1
The grammar G1 can be used to describe the set {0n1n|n ?1}.