Article Structure

Abstract

The language MIX consists of all strings over the three-letter alphabet {a, b, c} that contain an equal number of occurrences of each letter.

Introduction

The language MIX = {w E {a,b,c}* | lwla = IWIb = lwlc}

Head Grammars

A head grammar is a quadruple G = (N, 2, P, S), where N is a finite set of nonterminals, 2 is a finite set of terminal symbols (alphabet), S is a distinguished element of N, and P is a finite set of rules.

Decompositions of Strings in MIX

Henceforth, 2 = {a, b, c}.

A String in MIX That Has No 2-Decomposition

By Lemmas 3 and 4, in order to prove that there is no head grammar for MIX, it suffices to exhibit a string in MIX that has no 2-decomposition.