337 views
0 votes
0 votes
Remove the Null Productions

S → XY
X → Zb
Y → bW
Z → AB
W → Z
A → aA | bA | Λ
B → Ba | Bb | Λ

3 Answers

0 votes
0 votes
W1= {A,B}

W2= {A,B} – nullable variables

Vn= {S, X, Y, Z, W, A, B}

∑= {a,b}

 

P’= {S→ XY

X→ Zb | b

Y→ bW | b

Z→ AB | A | B

W→ Z

A→ aA | bA | a | b

B→ Ba | Bb | a | b}
0 votes
0 votes
Here A and B are nullable, because A→^ and B→^ but Z→AB, so from this we can say that Z is also nullable, also W→Z so W is also nullable. So new production is:-

S→ XY

X→ Zb | b

Y→ bW | b

Z→ AB | A | B

W→ Z

A→ aA | bA | a | b

B→ Ba | Bb | a | b

Related questions

0 votes
0 votes
1 answer
1
Biswajit Kumar asked Sep 13, 2023
195 views
Consider the following language definition:L= {(M) | M is a DFA and M accepts some string of the form ww^R for some w€ ΣL isA. RegularB. Context-free but not regularC....
0 votes
0 votes
2 answers
2
vrag asked Nov 12, 2021
214 views
Write the Regular expression using arden’s lemma
0 votes
0 votes
0 answers
3
Mk15 asked Nov 2, 2021
197 views
Construct a Reduced Grammer equivalent to the grammerS → aS/A/CC → aCbA → aB → aa
1 votes
1 votes
0 answers
4
Abhishek Kumar 40 asked Aug 7, 2018
726 views
can 0*1+1* generate 01 and 11 and 011?what would be the minimal dfa ?