Universal models

We know that Universal Turing Machines exist. Motivated by this, we can ask if universality also

arises with the other abstract models for formal languages that we have been considering.

Universal regular expressions

A universal regular expression $($URE$)$ is a regular expression U over the nine$-$symbol alphabet

$\{$a$,$ b$,\backslash$cup $,,(,),\backslash$epsi $,,$ $$\}$ such that, for every regular expression R over $\{$a$,$b$\}$ and every string x in

$\{$a$,$ b$\}$

$$

$,$

R matches x $$ U matches R$x$.$

The only role of $ here is to serve as a separator between the regular expression R and the string x$.$

This is analogous to our use of $ as a separator between an encoded Turing machine and its input,

when these two are combined and given as input to a Universal Turing Machine.

For example, if R is the regular expression $($a $\backslash$cup b$)$b

$$a and x is the string abba then R matches x

and R$x is the string $($a$\backslash$cup b$)$b

$$a$abba. So any URE U would have to match the string $($a$\backslash$cup b$)$b

$$a$abba.

But if y is the string baa then R does not match y$,$ so any URE U must not match R$y$,$ which is

$($a $\backslash$cup b$)$b

$$a$baa.

Universal context$-$free grammars

A universal context$-$free grammar $($UCFG$)$ is a context$-$free grammar U over the $18-$symbol

alphabet $\{$a$,$ b$,$ S$,$ T$,0,1,2,3,4,5,6,7,8,9,->,\backslash$epsi $,$ ;$,$ $$\}$ such that, for every context$-$free grammar G

over $\{$a$,$b$\}$ and every string x in $\{$a$,$ b$\}$

$$

$,$

G generates x $$ U generates G$x$.$

Again, the only role of $ is as a separator. We assume throughout that, apart from S$,$ nonterminals

have names consisting of the symbol T followed by a decimal positive integer, and that the semicolon

is used as a separator between production rules in order to encode a grammar as a string. $($We are

not using the vertical bar when encoding grammars here.$)$

For example, suppose G is the CFG

S $->$ aT

T $->$ aTb

T $->\backslash$epsi

This grammar can be encoded as

S$->$aT$1$;T$1->$aT$1$b;T$1->\backslash$epsi

We have two nonterminals, S and T$1,$ and three production rules. Suppose x is the string aaabb.

Then G$x is the string

S$->$aT$1$;T$1->$aT$1$b;T$1->\backslash$epsi $aaabb

Any UCFG U would have to match this string, since G generates x$,$ but it could not match U$y

where y $=$ bb$,$ since G cannot generate y$.$