Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
$\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$.
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.
