0
$\begingroup$

What is the meaning of lambda here: $$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$.

I know that lambda is used in the context of NFA?

Let's suppose we break down the expression to:$$(b+c)^*(a+\lambda)(b+c)^*$$

and to:$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$

How the above would generate an empty string? Somebody please guide me.

Zulfi.

$\endgroup$
1
$\begingroup$

$\lambda$ denotes the empty string, which is written "" in programming languages. The regular expression you give matches the empty string because you can choose each "$a+\lambda$" to match $\lambda$, and each "$(b+c)^*$" to match zero copies of $b+c$. So the expression matches, among other things, $\lambda\lambda\lambda\lambda\lambda\lambda\lambda$, which is just the same thing as $\lambda$.

$\endgroup$
  • $\begingroup$ How many a's can we generate from: (a+lambda)(a+lambda)? $\endgroup$ – user2994783 Nov 30 '19 at 13:54
  • $\begingroup$ Each bracket matches one $a$ or nothing. $\endgroup$ – David Richerby Nov 30 '19 at 14:06
1
$\begingroup$

To generate an empty string you take: $(b+c)^*$ as $\epsilon$, and all the following elements which have a Kleene-star as $\epsilon$ (I will use $\epsilon$ instead of $\lambda$).

Then you have: $$\epsilon(a+\epsilon)\epsilon(a+\epsilon)\epsilon$$ Which is equivalent to: $$(a+\epsilon)(a+\epsilon)$$

Which is essentially picking two options a or $\epsilon$ twice back to back. If you take $\epsilon$ transition each time, which is actually a transition that does not consume an input, it will essentially accept an empty string as input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.