How does Non-regular subset of Regular languages not violate Chomsky hierarchy?

40 Views Asked by At

Consider a language: $A = a^*b^* $ which is regular (and also context free). Consider another language: $B = \{ a^n b^n : n\geq 0\} $ which is Context-Free (non-regular). Clearly, $B$ is a proper subset of $A$. However, the Chomsky hierarchy states that $L_{reg}$ is a proper subset of $L_{CF}$. Then how are these two facts reconcilable? $A$ must belong to $L_{reg}$ and $B$ must belong to $L_{CF}-L_{reg}$. Then how can $B$ be a subset of $A$ when $L_{reg}$ and $L_{CF}-L_{reg}$ are disjoint?

1

There are 1 best solutions below

0
On BEST ANSWER

$A$ and $B$ are elements of the sets $L_{reg}$ and $L_{CF}$, so it doesn't matter if one is a subset of another.

As a simpler example, if $A = \{1,2\}$ and $B = \{1\}$, we can still have $R = \{A\}$ and $C=\{A,B\}$. Even though $B\in C-R$, $A\in R$, and $B\subset A$, it is clear that this doesn't pose a problem.