Thread: Regular Expression - need some explaining please.

the grammar below generates the language of regular expression 0*1(0 + 1)*:

S → A1B
A → 0A | λ
B → 0B | 1B | λ

Give the leftmost and rightmost derivations of the strings:
(a) 00101
(b) 1001
(c) 00011

Any help would be great, thankyou

S → A1B
A → 0A | λ
B → 0B | 1B | λ

(a) 00101

Well, let's consider the leftmost derivation. We have start with S -> A1B. Since A is at the left, we use its rule. A -> λ does not work since the word would start with 1. Therefore, we apply A -> 0A two times to get 00A1B. After that A disappears to λ. We need 0 after 1, so only the rule B -> 0B works at that point. After that, we use B -> 1B and B -> λ.

Altogether:

S -> A1B -> 0A1B -> 00A1B -> 001B -> 0010B -> 00101B -> 00101.

I hope this is right. If you have concrete difficulties, post them here.