CSL and LBA (Linear Bounded
Automata)
CSL: A language defined by a
CSG.
CSG is a grammar in
which the length of RHS of each rule is no smaller than that
of the LHS.
We
already know that every CSL is Recursive.
Now, we show that not every
Recursive set is CS.
THM11.1.2,
page-328
There is a Recursive
language on alphabet {1} that is not CS.
Proof:
Key
ideas:
1. Enumerating all CSG’s by representing
all productions of each CSG
by a long string (and equivalently a large integer) on a
five-letter alphabet
A = {/,
N, b, >,1}
2. All nonternimals are coded as N1
, N2 , N3 ,
3. Ni is
coded as Nbbb ... bbb
<- i times->
a. Let Li be the CSL generated by the i-th CSG in this enumeration, where
i=0,1,2,3,...
b. Consider the
language:
L = {1m | not in Lm }
c. We claim that this language is
not CS as it cannot be in this enumeration
because it is different from any Nk for any value of
k.
d. But it is Recursive
because
1m is in L if and
only if it is not in Lm
and since Lm is CS, “1m not in Lm“ is
computable.
So, “1m in L” is also computable. -> L is
Recursive.
QED.
Accepting automata:
LBA
1.
An NTM with two endmarkers: left and right:
{l ,
r}
2.
No left move beyond the left-marker, l.
And no right move beyond the
right-marker, r.
In fact, more than
that,
Q l R P
Q r L P
Above are the only permissible quadruples when the current tape symbols
is
either l or r.
3.
These two end-markers are NOT to be erased or inserted during any
computations.
4.
Final State, Qf , for which no quadruple is
defined.
5.
Acceptance is only by this final state.
Immediately entering this
final state, the TM (LBA) is to automatically stop in
accepting
the
given input string and this is the only way an LBA accepts an input
string.
6.
Also, initially an LBA is scanning the leftmost input symbol just to the right
of the
left end-marker.
Formally, an LBA accepts a
string U in T* if and only if
+
(1, Q1
,
lUr ) -> (
k, Qf , lU’r)
where the first component specifies the current
tape position number,
the second component specifies the current state
and the last specifies
the current tape contents surrounded by the two
end-markers.
THM2.1 : A language L on the alphabet A is CS if and only if there exists an LBA M such that L = LA (M) (The subscript A refers to strings only on the alphabet A in case in case the TM alphabet includes symbols not in A)
Lemma1: From a given CSG G with terminal set T, we can get an equivalent LBA M
such that L(G) = LT (M)
Lemma2: From Lemma1, it follows that given any CSL L on the alphabet A, we can
get an equivalent LBA such that L = LA (M).
The only concern is when L has l .
For this, we can include the following quadruple to the resulting LBA:
Q1 r
L Qf
Proof of lemma-1: Construction of an LBA M equivalent to a given arbitrary CSG G.
a. G has T and N (and S is the Start symbol)
b. T + N becomes the alphabet of M
c. G has m productions:
For each production, ui -> v i ; i=1,2, …, m
we let ui = a i 1 a i 2 a i 3 … a i ki
and
vi = b i 1 b i 2 b i
3 ... b i li
and a i ki+1 = ai ki+2 = … = a i li = B in case ki < li
d. States of M
· Q1: Initial state
· s : Search state (to repeatedly search for the bi 1 for any i to initiate
Production Undoing
_
· s : Return state (to reset the TM such that it enters Q1 pointing to the
leftmost tape symbol (and not the left end-marker)
· pi j : Undoing state (for i=1,2,…m and j=1,2,…, li) to precisely select
bi j to replace it with ai j
· qi j : Undoing state (for j=1,2, …, li-1) to move right before entering
pi
j+1
_
· t, t : Termination state to enter the Final state, Qf after confirming
that the tape contains nothing but S, the start symbol of the CSG.
· Qf : Final state.
e. Quadruples of M: Four phases:
(1) Initialization
Q1 a a s
Q1 a a t for every a in (T+N+{B}) but endmarkers
(2) Search (To locate the leftmost symbol of the RHS of any production rule
to initiate Production Undoing phase by entering a pi 1 state)
The search state will initially point to the leftmost tape symbol not
the left end-marker.
s a R s for every a in (T+N+{B}) but endmarkers
_
s
r
L
s
s bi 1 bi 1 pi 1 for every i=1,2, …, m
_ _
s a L s for every a in (T+N+{B}) but endmarkers
_
s l R Q1
(3) Production Undoing
pi j bi j ai j qi j for i=1,2…,m and j=1,2…, li-1
qi j ai j R pi j+1 for i=1,2…,m and j=1,2…, li-1
_
pi li bi li ai li s (for i=1,2…,m) to initiate Search phase
after undoing the last symbol of a production rule.
pi j B R pi j (for i=1,2…,m and j=2,3,…, li) to
skip all intervening blanks in looking for the next
symbol of the same rule’s RHS string.
(4) Termination (Initially, the first termination state, t , points to the leftmost tape
symbol not the left end-marker)
During this phase, the TM enters the final state Qf if and only if the tape
contains nothing but the grammar start symbol and the two end markers and
Blanks.
t
B
R
t
_
t S R t
_ _
t B R t
_
t r R Qf
From the construction of this LBA, The LBA will enter its final state if and only if
the final tape contents contains nothing but the start symbol, S, of the CSG to indicate that there is a derivation of the input string starting from S by this CSG.
So far, we only showed the half of the equivalence of CSL’s and LBA
The other half is to show that we can get a CSG that is equivalent to a given arbitrary LBA. Lemma-5, page-336 shows this.
Closure Properties of
CSL’s
CSL’s are closed under
1. Set union (THM1.3, page-329)
Proof: We want to identify a CSG that defines the union of any two given
CSL’s.
a. Assume that given two CSL’s are defined by two CSG’s, G1 and G2
b. Assume further that the nonterminal sets of G1 and G2 are disjoint, i.e., there is no common nonterminal to both grammars.
c. The grammar we want will include all production rules of G1 and G2
and additionally the following rules:
S -> S1 // S1 is the Start symbol of G1
S -> S2 // S2 is the Start symbol of G2
2. Set intersection (THM3.1, page 337)
3. Complementation : For a long time, it was not known.
THM3.3, page-343
4. Concatenation
5. Positive (transitive) closure.
Open problem:
Is there any CSL that is not accepted by a DLBA???
That is, DLBA = NLBA??? Or
CSL’s = DLBA???