L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}, where t is the string after s in a lexicographic ordering of {a,b}}.

Chapter24ChomskyHierarchyandBeyondFile.ppt

Home >Computer Science homework help >L = { <M,t> : t ∈ L(M) and s ∉ L(M), t,s ∈ {a,b}*, where t is the string after s in a lexicographic ordering of {a,b}*}.

The Chomsky Hierarchy
and Beyond

Chapter 24

Is There Anything In Between PDAs and Turing Machines?

PDAs aren’t powerful enough.

Turing machines lack even a decision procedure for the acceptance problem.

Linear Bounded Automata

A linear bounded automaton is an NDTM the length of whose tape is equal to |w| + 2.

Example: AnBnCn = {anbncn : n  0}

qaabbccqqqqqqqqq

Linear Bounded Automata

A language is context sensitive iff there exists an LBA that accepts it.

Note: It is not known whether, for every nondeterministic LBA there exists an equivalent deterministic one.

The Membership Question for LBAs

Let L = {<B, w> : LBA B accepts w}. Is L in D?

… q a b b a q …

How many distinct configurations of B exist?

The Membership Question for LBAs

Let L = {<B, w> : LBA B accepts w}. Is L in D?

… q a b b a q …

How many distinct configurations of B exist?

MaxConfigs = |K|  ||(|w|+2)  (|w| + 2)

The Membership Question for LBAs

Theorem: L = {<B, w> : LBA B accepts w} is in D.

Proof: If B runs for more than MaxConfig steps, it is in a loop and it is not going to halt.

M is an NDTM that decides L:

M(<B, w>) =

1. Simulate all paths of B on w for MaxConfig steps or until

B halts, whichever comes first.

2. If any path accepted, accept. Else reject.

Since, from each configuration of B there are a finite number of

branches and each branch is of finite length, M will be able to try

all branches of B in a finite number of steps. M will accept the

string <B, w> if any path of B accepts and it will reject the string

<B, w> if every path of B on w either rejects or loops.

Grammars, Context-Sensitive Languages, and LBAs

CS Language

Grammar

LBA

Accepts

Context-Sensitive Grammars and Languages

A context-sensitive grammar G = (V, , R, S) is an unrestricted grammar in which R satisfies the following constraints:

● The left-hand side of every rule contains at least one

nonterminal symbol.

● No length-reducing rules, with one exception:

Consider: S  a S b

S   /* length reducing

Context-Sensitive Grammars and Languages

A context-sensitive grammar G = (V, , R, S) is an unrestricted grammar in which R satisfies the following constraints:

● The left-hand side of every rule contains at least one

nonterminal symbol.

● No length-reducing rules, with one exception:

● R may contain the rule S  .

If it does, then S does not occur on the right hand side

of any rule.

Context-Sensitive Grammars and Languages

Example of a grammar that is not context-sensitive:

S  aSb

S  

An equivalent, context-sensitive grammar:

Context-Sensitive Grammars and Languages

Example of a grammar that is not context-sensitive:

S  aSb

S  

An equivalent, context-sensitive grammar:

S  

S  T

T  aTb

T  ab

AnBnCn

S  aBSc

S   /* Not a CS rule

Ba  aB

Bc  bc

Bb  bb

AnBnCn

Not a CS grammar. But there is an equivalent one that isolates the epsilon rule at the beginning.

{w  {a, b, c}* : #a(w) = #b(w) = #c(w)}

S  ABCS

S  

AB  BA

BC  CB

AC  CA

BA  AB

CA  AC

CB  BC

A  a

B  b

C  c

Equal Numbers of a’s, b’s, and c’s

Again, not a CS grammar. But easy to fix.

WW = {ww : w  {a, b}*}

S  T# /* Generate the wall exactly once.

T  aTa /* Generate wCwR.

T  bTb 

T  C 

C  CP /* Generate a pusher P

Paa aPa /* Push one character to the right

to get ready to jump.

Pab  bPa 

Pba  aPb 

Pbb  bPb 

Pa#  #a /* Hop a character over the wall.

Pb#  #b 

C#  

Not a CS grammar. Harder to fix because it’s no longer possible to erase the pushers and the C. So they have to be encoded as part of another symbol.

The Membership Question for Context-Sensitive Grammars

Let L = {<G, w> : csg G generates string w}. Is L in D?

Example:

S  aBSc

S  aBc

Ba  aB

Bc  bc

Bb  bb

S  aBSc  aBaBScc  aaBBScc …

L = {<G, w> : CSG G generates string w} is in D.

Proof: We construct an NDTM M to decide D. M will explore all

derivations that G can produce starting with S. Eventually one of

the following things must happen on every derivation path:

● G will generate w.

● G will generate a string to which no rules can be applied.

● G will keep generating strings of the same length. Since there

are a finite number of strings of a given length, G must eventually

generate the same one twice. The path can be terminated since

it is not getting any closer to generating w.

● G will generate a string s that is longer than w.

Since G has only a finite number of choices at each derivation step

and since each path that is generated must eventually halt, the

Turing machine M that explores all derivation paths will eventually

halt. If at least one path generates w, M will accept. If no path

generates w, M will reject.

Context-Sensitive Languages and Linear Bounded Automata

Theorem: The set of languages that can be generated by a

context-sensitive grammar is identical to the class that can

be accepted by an LBA.

Proof: (sketch)

● Given a CSG G, build a two-track LBA B such that

L(B) = L(G). On input w, B keeps w on the first track. On

the second track, it nondeterministically constructs all

derivations of G. As soon as any derivation becomes

longer than |w|, stop.

● From any LBA B, construct a CSG that simulates B.

Languages and Machines

Context-sensitive

Context-free

DCF

Regular

FSMs

DPDAs

NDPDAs

LBAs

Turing machines

Theorem: The CS languages are a proper subset of D.

Proof: We divide the proof into two parts:

● Every CS language is in D: Every CS language L is

accepted by some LBA B. The Turing machine that

performs a bounded simulation of B decides L.

● There exists at least one language that is in D but that is

not context-sensitive: It is not easy to do this by actually

exhibiting such a language. But we can use diagonalization

to show that one exists.

Context-Sensitive Languages vs. D

Using Diagonalization

Create an encoding for context-sensitive grammars:

x00ax00a;x00x01;x01bx01b;x01b

EnumG is the lexicographic enumeration of all encodings of CSGs with  = {a, b}.

Enuma,b is the lexicographic enumeration of {a, b}*.

Because {<G, w> : CSG G generates string w}, is in D, there exists

a TM that can compute the values in this table as they are needed.

String 1	String 2	String 3	String 4	String 5	…….
Grammar 1	1	0	0	0	0	…..
Grammar 2	0	1	0	0	0	…..
Grammar 3	1	1	0	0	0	…..
Grammar 4	0	0	1	0	0	…..
…	1	1	1	0	0	…..

Diagonalization, Continued

Define LD = {stringi : stringi  L(Gi)}. LD is:

● Recursive because it is decided by the following Turing

machine M:

M(x) =

1. Find x in the list Enuma,b. Let its index be i.

2. Lookup cell (i, i) in the table.

3. If the value is 0, x is not in L(Gi) so x is in L. Accept.

4. If the value is 1, x is in L(Gi) so x is not in L. Reject.

● Not context-sensitive because it differs, in the case of at least

one string, from every language in the table and so is not

generated by any context-sensitive grammar.

Theorem: The context-free languages are a proper subset of the

context-sensitive languages.

Proof: We divide the proof into two parts:

● We know one language, AnBnCn, that is context-sensitive but

not context-free.

● If L is a context-free language then there exists some context-free

grammar G = (V, , R, S) that generates it:

● Convert G to G in Chomsky normal form

● G generates L – {}.

● G has no length-reducing rules, so is a CSG.

● If   L, add to G the rules S   and S  S.

● G is still a context-sensitive grammar and it generates L.

● So L is a context-sensitive language.

Context-Sensitive vs Context-Free

The context-sensitive languages are closed under:

● Union

● Concatenation

● Kleene star

● Intersection

● Complement

Closure Properties

Theorem: The CSLs are closed under union.

Proof: By construction of a CSG G such that L(G) = L(G1)  L(G2):

If L1 and L2 are CSLs, then there exist CSGs:

G1 = (V1, 1, R1, S1) and

G2 = (V2, 2, R2, S2) such that L1 = L(G1) and L2 = L(G2).

Rename the nonterminals of G1 and G2 so that they are disjoint

and neither includes the symbol S.

G will contain all the rules of both G1 and G2. Add to G a new start symbol, S, and two new rules:

S  S1 and S  S2.

So G = (V1  V2  {S}, 1  2,

R1  R2  {S  S1, S  S2}, S).

Closure Under Union

Theorem: The CSLs are closed under concatenation.

Proof: By construction of a CSG G such that L(G) = L(G1) L(G2):

If L1 and L2 are CSLs, then there exist CSGs G1 = (V1, 1, R1, S1) and G2 = (V2, 2, R2, S2) such that L1 = L(G1) and L2 = L(G2).

Let G contain all the rules of G1 and G2. Then add a new start symbol, S, and one new rule, S  S1 S2.

Problem:

S1 S2

a a A a a a

The subtrees may interact.

Closure Under Concatenation

A CSG G = (V, , R, S) is in nonterminal normal form iff all rules in R are of one of the following two forms:

●   c, where  is an element of (V - ) and c  ,

●   , where both  and  are elements of (V - )+.

A  aBBc is not in nonterminal normal form.

aAB  BB is not in nonterminal normal form.

Nonterminal Normal Form

Theorem: Given a CSG G, there exists an equivalent nonterminal

normal form grammar G such that L(G) = L(G).

Proof: The proof is by construction.

converttononterminal(G: CSG) =

1. Initially, let G = G.

2. For each terminal symbol c in , create a new nonterminal symbol

Tc. Add to RG the rule Tc  c.

3. Modify each of the original rules so that every occurrence of a

terminal symbol c is replaced by the nonterminal symbol Tc.

4. Return G.

Nonterminal Normal Form

AA  aBBc becomes AA  TaBBTc

Ta  a

Tc  c

aAB  BB becomes TaAB  BB

S1 S2

a a A a a a

Now the subtrees will be:

Closure Under Concatenation

S1 S2

a a A Ta a a

We prevent them from interacting by standardizing apart the nonterminals.

To build a grammar G such that L(G) = L(G1) L(G2), we do the following:

1. Convert both G1 and G2 to nonterminal normal form.

2. If necessary, rename the nonterminals of G1 and G2 so

that the two sets are disjoint and so that neither includes

the symbol S.

3. Let G = (V1  V2  {S}, 1  2,

R1  R2  {S  S1 S2}, S).

Concatenation, Continued

The membership problem is decidable, although no efficient procedure is known.

1.bin

Real Plants

http://algorithmicbotany.org/papers/#abop

These two images from the main page: http://algorithmicbotany.org/papers/#abop

Let G be the L-system defined as follows:

 = {, }.

 = .

R = { ( | )  ()   ,

( | )  ( | )  ,

()  ()   ,

()  ( | )  ,

( | )  ()   ,

( | )  ( | )  ,

()  ()   ,

()  ( | )   }.

Sierpinski Triangles, Again

Theorem: Context-sensitive L-systems and Turing machines can

simulate each other.

Proof: The computation of any L-system can be simulated by a

Turing machine that implements the algorithm L-system-interpret.

So it remains to show the other direction, by construction.

We show that deterministic TM M, on input w, halts in some

halting state q and with tape contents v iff L-system L converges

to the static string qv.

Define L as follows:

● Let L be M, augmented by adding the symbols y, n, and h, plus

one distinct symbol for each nonhalting state of M. Assume that 0

encodes M’s start state.

Equivalence of Context-Sensitive
L-Systems and Turing Machines

Let  encode M’s initial configuration as:

qq0qwqq.

Let the rules of L encode M’s transitions. The action of a Turing

machine is very local. Consider:

ga4bcde.

The read/write head can move one square and the character under it

can change. To decide how to rewrite some character in the working

string, it is sufficient to look at one character to its left and two to its

right. If there is no state symbol in that area, the symbol gets rewritten

as itself (no rule needed). For all other combinations, add to R rules

that cause the system to behave as M behaves. Finally, add rules so

that, if h, y, or n is generated, it will be pushed all the way to the left,

leaving the rest of the string unchanged. Add no other rules to R.

L will converge to qv iff M halts, in state q, with v on its tape.

Defining L, Continued