Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 12I (Automata and Formal Languages)

Table of contents
- a 12I
  - Solution a
- b 12I
  - Solution b
- c 12I
  - i c
    - Solution i
  - ii c
    - Solution ii
- d 12I
  - Solution d

a

Solution

A variable-based grammar is

(N, Σ, P, S)

with disjoint nonterminals and terminals, productions between words over

N \cup Σ

, and start variable

S

. Its language is

{w \in Σ^{*} : S \Rightarrow^{*} w}

.

b

Solution

A type-2 rule is

A \to α

with one nonterminal

A

on the left; a type-2 grammar and its language are context-free language s. The required repetition criterion is the pumping lemma for context-free languages.

c

i

Solution

This language is context-free. One grammar is

S \to a S c ∣ a T c, T \to b T ∣ b,

which independently chooses at least one outer

a, c

pair and at least one

b

.

ii

Solution

It is not context-free. Intersecting it with the regular language

a^{*} b^{*} c^{*}

would give

{a^{n} b^{n} c^{n} : n \geq 0}

, which violates the pumping lemma for context-free languages. Context-free languages are closed under intersection with regular languages.

d

Solution

No production introduces

A

, so the two rules containing

A

are unreachable. The effective derivations are

S \Rightarrow a^{n} b C (BC)^{n - 1} \Rightarrow a^{n} b^{n} C^{n} \Rightarrow a^{n} b^{n} c^{n} .

Thus the language is ${a^{n} b^{n} c^{n} : n \geq 1}$ , which is not context-free language, although the displayed grammar itself also visibly has non-type-2 left sides.

 Ancestors (9)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version