# Context-free language and regular expressions

I have the following context-free language:

S -> ASa | b
A -> aA | a


I don't understand why this is not regular. I first said that it's generated by the regular expression a+ba+. The following is regular however

S -> ASa | b
A -> aA | e


e stands for the empty string. I don't understand their differences.

The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\{a^nba^m|n\geq m\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^*ba^+$ which is regular.

In the first case, we can write this in the following form, if we admit the Kleene algebra of regular expressions on the right: $$S → a a^* S a | b.$$ As an inequality in set theory it may be written as $$S ⊇ \{a\}\{a\}^* S \{a\} ∪ \{b\},$$ but, for convenience, we will keep to the regular expression notation and use this only as a point of reference. In algebraic form, in Kleene algebra, it can equivalently be expressed as the fixed-point inequation $$S ≥ a a^* S a + b,$$ whose least fixed point yields the language in question. That is also the case for the corresponding set-theoretic inequation.

In addition, the least solution is also a solution to its corresponding equation: $$S = a a^* S a + b.$$

Define the following: $$x \backslash A = \{ m ∈ M: x m ∈ A \}\quad A_0 = A ∩ \{e\}$$ for subsets $$A ⊆ M$$, $$x ∈ X = \{a,b\}$$, where $$M = X^*$$ is the underlying word algebra (i.e. the underlying Monoid). Note, in particular, the product rule: $$x \backslash (A B) = (x \backslash A) B + A_0 (x \backslash B).$$

The minimal deterministic automaton is derived by systematically applying this to the top-level expression $$S = a a^* S a + b$$ and to all expressions derived from it.

In fact, there is a single infinite state diagram - The Universal State Diagram - that contains the state diagrams of every single minimal deterministic automaton - both finite and infinite - over $$X = \{a,b\}$$. Its states consist of all the subsets of $$M = X^*$$, and, for each subset $$A ⊆ M$$, the state transitions on each $$x ∈ X$$ are $$A \overset{x}→ x\backslash A$$. Its final states are all the subsets $$A ⊆ M$$ for which $$A_0 = \{e\}$$.

The portion of the diagram that is accessible from a subset $$A ⊆ M$$ - whether that subdiagram is infinite or finite - is the state diagram for the minimal deterministic automaton of $$A$$. If it is finite, then $$A$$ is regular. If it is not finite, then $$A$$ is not regular.

The expressions derived from $$S$$, besides $$S$$ itself, ultimately, prove to be the following: $$P(n) = e + a + a^2 + ⋯ + a^n,\quad Q(n) = a P(n),\quad R(n) = a^* S Q(n),\quad (n = 0, 1, 2, ⋯),$$ and we have $$a\backslash S = a\backslash (a a^* S a) + a\backslash b = a^* S a + 0 = a^* S a = R(0),\\ b\backslash S = b\backslash (a a^* S a) + b\backslash b = 0 + e = e = P(0),\\ S_0 = 0,$$ where the $$0$$ of the underlying Kleene algebra denotes the empty set.

Repeating the process on the $$R$$ expressions, noting that, by virtue of the identity $$a^* = e + a a^*$$, we have the identity $$a\backslash (a^* A) = a\backslash A + a\backslash (a a^* A) = a\backslash A + a^* A,$$ we can write, for $$n = 0, 1, 2, ⋯$$: $$a\backslash R(n) = a\backslash (a^* S Q(n)) = (a\backslash S) Q(n) + a^* S Q(n) = a^* S Q(n+1) = R(n+1),\\ b\backslash R(n) = (b\backslash S) Q(n) = e Q(n) = Q(n),\\ {R(n)}_0 = 0.$$

Repeating the process on the $$Q$$ and $$R$$ expressions, we get, for $$n = 0, 1, 2, ⋯$$: $$a\backslash Q(n) = P(n),\quad b\backslash Q(n) = 0,\quad {Q(n)}_0 = 0,\\ a\backslash P(n+1) = P(n),\quad a\backslash P(0) = 0,\quad b\backslash P(n) = 0,\quad {P(n)}_0 = e.$$

The resulting deterministic automaton is an infinite state automaton, with start state $$S$$, final states $$P(n)$$ for $$n = 0, 1, 2, ⋯$$, and state transitions: $$S \overset{a}→ R(0),\quad S \overset{b}→ P(0),\\ R(n) \overset{a}→ R(n+1),\quad R(n) \overset{b}→ Q(n),\\ Q(n) \overset{a}→ P(n),\quad P(n+1) \overset{a}→ P(n),$$ for $$n = 0, 1, 2, ⋯$$. Because it is indexed by a counter, and the state transitions have the right kind of symmetry with respect to the counter, then the automaton can be folded into a one counter automaton.

Depending on the kind of symmetries possessed by the state diagram, if it is infinite, the corresponding automaton might be "foldable" into one of the specialized classes of infinite state automaton usually covered in the literature, such as push-down automata, counter automata, one-tape automata, and so on.

For the second example, recycling the letters used previously, we have the corresponding fixed-point inequation: $$S ≥ a^* S a + b.$$

This time, the only states accessible from $$S$$ are those corresponding to: $$S,\quad R = a^* S a a^*,\quad Q = a a^*,\quad P = a^*,\quad e.$$ The key calculations are those for $$a\backslash S$$ and $$a\backslash R$$. The others are trivial and yield the transitions $$S \overset{b}→ e$$, $$R\overset{b}→ Q$$ and $$Q \overset{a}→ P$$ and $$P \overset{a}→ P$$. The final states are $$P$$ and $$e$$.

First, we have \begin{align} a\backslash S &= a\backslash(a^* S a + b)\\ &= a\backslash(a^* S a) + a\backslash b\\ &= a^* S a + (a\backslash S) a + 0\\ &= a^* S a + (a\backslash S) a. \end{align} This is recursive, and all of this should be understood as taking place under the "least fixed point" regime, which means you're actually seeking out the least fixed point solution $$X = a\backslash S$$ to: $$X ≥ a^* S a + X a.$$ That can be solved entirely within the Kleene algebra of regular expressions, since in general, the least fixed point solution to $$X ≥ u + X v$$ is $$u v^*$$. So, we have $$a\backslash S = X = a^* S a a^* = R.$$

For $$a\backslash R$$, we have \begin{align} a\backslash R &= a\backslash(a^* S a a^*)\\ &= a^* S a a^* + (a\backslash S) a a^*\\ &= a^* S a a^* + a^* S a a^* a a^*\\ &= a^* S a a^* (e + a a^*)\\ &= a^* S a a^* a^*\\ &= a^* S a a^*\\ &= R, \end{align} using the Kleene-algebraic identities $$a^* = e + a a^*$$ and $$a^* a^* = a^*$$.

Therefore, the remaining state transitions are $$S \overset{a}→ R$$ and $$R \overset{a}→ R$$.

The corresponding fixed-point system can be written down, and is: $$S ≥ a R + b e,\\ R ≥ a R + b Q,\\ Q ≥ a P,\\ P ≥ a P + e,\\ e ≥ e.$$ It is affine to the right. Footnote: "affine" means degree one, while "linear" actually means degree one with zero constant coefficients. So, when people call such systems "right-linear", that's wrong. It's right-affine.

All finite systems, that are affine to one side, can be solved entirely within the Kleene algebra of regular expressions. Here, the least fixed point solution is: $$e = e,\quad P = a^*,\quad Q = a a^*,\quad R = a^* b a a^*,\quad S = a a^* b a a^* + b.$$ For the top-level expression $$S$$, that yields the regular expression $$a a^* b a a^* + b$$.

See, in the CFG grammar you need to store the value of n and m in order to compare the condition i.e. n>= m.So memory is required,preferably a stack.Whereas, in the regular grammar its either b or any string ending with ba. You don't need anything to remember to satisfy the grammar,as there is no such condition where you need to store the value.

• I am not the original down-voter but your answer is very vague and, in parts, incorrect. What does it mean to say "in the CFG Grammar, you need to store the value of $n$ and $m$"? $n$ and $m$ are not mentioned anywhere in the question. And a grammar is just a set of rules for producing strings: you don't need to store any integers to do that. Why is a stack the preferred way to remember integers? The regular grammar does not generate $b$ or any string ending $ba$: for example, it includes $abaa$ but not $bba$. Commented Feb 14, 2014 at 12:49