Each of the following CFGs has a production using the symbol and yet is not

Question:

Each of the following CFGs has a production using the symbol Λ and yet Λ is not a word in its language. Using the algorithm in this chapter, show that there are other CFGs for these languages that do not use Λ-productions:

(i) 

S → aX I bX
X → a I b I Λ

(ii) 

S → aX I bS I a I b
X → aX |a | Λ

(iii) 

S → aS I bX
X → aX I Λ

(iv) 

S → XaX I bX
X → XaX I XbX I Λ

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: