# new language accepted by FA when new transitions are added to a FA?

found this question online and I am trying to solve this question. I have solved this question but I think I might be missing some cases. Could someone verify if my answers are correct?

Let N = (Σ ∪ {λ}, Q, δ, q0, {qf }) be a λ − NFA and let L = L(N) be the language accepted by N. For N assume q0 has no incoming transitions and qf has no outgoing transitions. For each of the following FAs that are modifications of N describe the language accepted by each in terms of L.

(a) A λ-transition is added from qf to q0.

(b) Add a λ-transition from q0 to every state reachable from q0 along a path with labels that may be λ or symbols from Σ.

(c) Add a λ-transition to qf from every state that reach qf along some path.

(d) The FA where both (b) and (c) are done.

a) L+

b) For this one I have defined a function suff, this takes all the valid strings in the original Language and generates new stings from them. For example, if L = {112,12} where alphabet is {1,2}

Then, suff(L) means suff(112) + suff(12)

where suff(112) = {112,12,2}, keeps chopping off the first symbol until u get empty string

Similarly, suff(12) = {12,2}

So, the final answer would be suff(L) + the empty string. (Is this correct?)

C) for this one, I defined pre which is similar to suff but chops off the last symbol.

pre(123) = {123,12,1}
pre(112) = {112,11,1}


So, the final ans is pre(L) + empty string

d) I need help with this one..

• What does L+ mean? – kotu Feb 18 at 19:43
• Kleene plus operator applied to language L – ray an Feb 18 at 19:53
• You mean this thing, right? en.wikipedia.org/wiki/Kleene_star – kotu Feb 18 at 19:55
• – ray an Feb 18 at 19:58
• You should look at the first three categories of en.wikipedia.org/wiki/Substring – Nathaniel Feb 18 at 21:57

Hint for (d): Let's say $$s = s_1s_2...s_k \in L$$, and on input $$s$$ the original transition function follows the path $$P = q_0, q_1... q_f$$. Let $$q_{s_i}$$ denote the state $$q_i$$ closest to $$q_f$$ in $$P$$ after only reading up to $$s_i$$ in the original NFA. What are the strings can I generate by doing the following in the NFA defined by (d)? $$\lambda$$-transition from $$q_0$$ to $$q_{s_i}$$, follow $$P$$ up to $$q_{s_j}$$ (for any $$1 < i < j < k$$), and then $$\lambda$$-transition to $$q_f$$ and accept.