Machine Types That Accept Non-regular Languages
Machine types that accept non-regular languages: Consider the language
L1 = {aibjck | i, j, k ≥ 0 ∧ if i = 1 then j = k}.
In all the strings in this language, the characters a, b, and c appear in that order, with b’s and c’s being equal in number if the number of a’s is 1. This language can obviously be handled using a DPDA, using its stack. In fact,
reverse(L1)
can also be handled using a DPDA, as the finite-state control can remember whether the number of b’s and c’s were equal by the time the a (or a’s) appear. Now consider
L2 = {aibjckdm| i, j, k,m ≥ 0 ∧ if i = 1 then j = k else k = m}.
This language can still be processed using only one stack, as the matching between b’s and c’s or c’s and d’s (whichever is to occur) can be decided by first seeing the a’s. No such luck awaits
reverse(L2),
which has to have two decisions, (whether the number of b’s and c’s match, or whether the number of c’s and d’smatch), in hand by the time the a (or a’s) arrive. Clearly, these two decisions cannot be generated using a single stack, thus showing that reverse(L2) cannot be processed by a DPDA. The same can be concluded about
L3 = {ww | w ∈ {0, 1}∗}
also, as the second w’s head must be matched against the first w’s head which, unfortunately, is at the bottom of the stack. It turns out (as we shall demonstrate later) that
L4 = L3
indeed can be processed using a single stack push-down automaton.
One obvious solution to handling L3, as well as reverse(L2), would be to employ two stacks instead of one. Unfortunately this gives more power than necessary (the machine becomes as powerful as a Turing machine). Another machine type, the linear bounded automaton (LBA), can be used. An LBA has finite control as well as a tape such that it can read/write only the region of the tape in which the input initially appeared. In addition, an LBA has a finite tape alphabet that may (and typically does) contain Σ, the input alphabet, plus (typically) many additional symbols. Exploiting the ability to repeatedly scan the input, an LBA can decide membership in all the languages listed above. By the same token, an LBA can decide membership in the language
{anbncn| n ≥ 0}
as well as
{an bn2| n ≥ 0}.
We later present languages that cannot be decided using LBAs. To handle the full generality of languages, we remove the restriction on LBAs that they can write only where the input is presented, thus obtaining a Turing machine.