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$

2 Answers 2

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$
2
  • $\begingroup$ How many a's can we generate from: (a+lambda)(a+lambda)? $\endgroup$ Nov 30, 2019 at 13:54
  • $\begingroup$ Each bracket matches one $a$ or nothing. $\endgroup$ Nov 30, 2019 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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