Skip to main content

CFG for aᵐbⁿ with m ≥ n

Short answer

Grammar: S → aSb | aS | ab. Derivation for aaab: S ⇒ aS ⇒ aaS ⇒ aaab. Parse tree: root S with children a, S; that S with a, S; that S with a, b (leaves a a a b).

Construct a CFG for the language L(G) = {aᵐbⁿ : m, n > 0, m ≥ n}. Use the grammar to generate the string "aaab". Also draw the parse tree.

L = { aᵐbⁿ : m ≥ n ≥ 1 }. Each b is matched with an a, and the extra a's (m − n of them) can be placed anywhere on the left, because all the a's come first.

Grammar

G = ({S}, {a, b}, P, S) with

S → aSb | aS | ab
  • S → aSb adds one matched a…b pair.
  • S → aS adds an extra a (so m can exceed n).
  • S → ab ends the derivation with the last pair, ensuring n ≥ 1.

Every string is of the form aᵐbⁿ with m ≥ n ≥ 1: only a's are added on the left and b's on the right, and each b is created together with an a.

Derivation of aaab (m = 3, n = 1)

S ⇒ aS ⇒ aaS ⇒ aaab

The rules used are S → aS twice, then S → ab.

Parse tree

            S
          / |
         a  S
          / |
         a  S
           / \
          a   b

Reading the leaves from left to right gives a, a, a, b = aaab. Each interior node is labelled S, and the bottom S uses S → ab.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →