Language of grammar; grammar for strings not ending in ab

(i) Language of G

G has non-terminals S, A; terminals a, b, c; start symbol S; productions: S → aSb, aS → Aa, Aab → c.

S can only be rewritten by S → aSb, so the sentential forms are aⁿ S bⁿ (n ≥ 1). The only way to remove S is the rule aS → Aa, applied to the last a next to S:

S ⇒ aSb ⇒ aaSbb ⇒ ... ⇒ aⁿ S bⁿ
aⁿ S bⁿ ⇒ aⁿ⁻¹ (aS) bⁿ ⇒ aⁿ⁻¹ A a bⁿ        (using aS → Aa)
        ⇒ aⁿ⁻¹ c bⁿ⁻¹                         (using Aab → c, since A a b appears)

Example n = 2: S ⇒ aSb ⇒ aaSbb ⇒ aAabb ⇒ acb. For n = 1: S ⇒ aSb ⇒ Aab ⇒ c.

No other rule can apply at any step (a terminal string cannot contain S or A), so

L(G) = { aᵏ c bᵏ : k ≥ 0 } (c, acb, aacbb, ...). A search over all derivations up to length 9 gave exactly these strings.

(ii) Grammar for strings over {a, b} not ending with ab

The set consists of: the empty string, the string b, strings ending in a, and strings ending in bb (a string ending in b is bad only if the symbol before it is a).

Context-free grammar G = ({S, X}, {a, b}, P, S) with

S → Xa | Xbb | b | ε
X → aX | bX | ε

X generates any string over {a, b}. Examples: abba (X = abb, then a), abb (X = a, then bb), aab is not generated.

Equivalent regular grammar (from the DFA that tracks "last symbol a", "last two symbols ab"):

S → aA | bS | ε
A → aA | bB | ε
B → aA | bS

Here A means "the last symbol read is a" and B means "the string read so far ends in ab". B has no ε-rule, so a string ending in ab can never finish. Both grammars were checked against all strings up to length 8.