---
title: "Language of grammar; grammar for strings not ending in ab"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:language-of-grammar-and-grammar-not-ending-ab"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/language-of-grammar-and-grammar-not-ending-ab
site: BCT Engineering
---

# Language of grammar; grammar for strings not ending in ab

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2075 Bhadra, 4+4 marks
- Video: [Derivations from a Grammar](https://www.youtube.com/watch?v=ejXgLRSIxsA) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/language-of-grammar-and-grammar-not-ending-ab
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

i) Find the language L(G) over {a,b,c} generated by the grammar G with production: S→aSb, aS→Aa, Aab→c. ii) Write a grammar that generates the string over {a,b} not ending with ab.

## Short answer

L(G) = {a^k c b^k : k ≥ 0}. A grammar for strings not ending with ab: S → Xa | Xbb | b | ε, X → aX | bX | ε.

## Answer

#### (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:

```text
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

```text
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"):

```text
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Since S only rewrites by S→aSb, what do the sentential forms look like before S is removed?
   A. a^n S b^m with any m
   B. S^n a b
   C. a S^n b
   D. a^n S b^n
   Answer: D. Each use of S→aSb adds one a and one b. (Key point: Sentential forms)

2. How is S removed and how does c appear?
   A. aS→Aa then Aab→c
   B. S→ε then aab→c
   C. Aab→S then aS→c
   D. S→c directly
   Answer: A. The last a next to S becomes Aa, then A a b is replaced by c. (Key point: Role of rules)

3. What is L(G)?
   A. { a^n b^n : n ≥ 1 }
   B. { a^k c b^m }
   C. { a^k c b^k : k ≥ 0 }
   D. { c }
   Answer: C. The derivation leaves c with equal numbers of a's and b's around it. (Key point: Language of G)

4. Which strings does the grammar S→Xa | Xbb | b | ε generate?
   A. Strings ending with ab
   B. Strings ending only in a
   C. All strings over {a, b}
   D. Strings over {a, b} not ending with ab (e.g. ε, b, abba, abb)
   Answer: D. A string ending in b is allowed only as b alone or when preceded by b. (Key point: Not ending in ab)

## Related in Discrete Structure

- [NFA and DFA from grammar σ→aA|bB](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-aa-bb) — Discrete Structure, chapter 2, asked 2×
- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2
- [NFA and DFA from grammar σ→bσ|aC](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-bsigma-ac) — Discrete Structure, chapter 2, asked 4×
- [NFA and DFA from grammar with A, B rules](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-with-a-b-productions) — Discrete Structure, chapter 2, asked 2×
- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2

## Related in other subjects

- [NFA for (ab*a ∪ b*aa)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-ab-star-a-union) — Theory of Computation, chapter 2
- [CNF: S→ASB|ε, A→aAS|a, B→...](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-asb) — Theory of Computation, chapter 3
- [Voltage across string discs is not uniform](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Astring-voltage-not-uniform) — Power System Analysis I, chapter 2, asked 3×
- [Rod AB sliding over wheel C](https://www.bctengineer.com/question.md?key=semester_3%2Fapplied_mechanics_dynamics%3Arod-ab-over-wheel-c-velocity) — Applied Mechanics (Dynamics), chapter 4