0
$\begingroup$

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..

$\endgroup$
5
1
$\begingroup$

Your answers to (a), (b), and (c) seem correct to me. Here's something to think about for (d).

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.

$\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.