theoretical CS

CFG to Chomsky steps

1. new start state

2. Eliminate all E rules

3. Remove all unit rules

4. Fix the rest

        (S → V1V2 | t | E

         V → V1V2 | t )

If A is a context free language, then there is a number p (the pumping length) where, if s E A and has at least p symbols, that is, |s| >= p, the string s can be divided into five substrings s = uvxyz satisfying the conditions…

1. For all i >= 0 and i E Z, uv^ixy^iz E A

2. |xy| > 0

3. |vxy| <= p

o

o