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

Improve this question
$\endgroup$
5
  • $\begingroup$ What does L+ mean? $\endgroup$ Commented Feb 18, 2021 at 19:43
  • $\begingroup$ Kleene plus operator applied to language L $\endgroup$ Commented Feb 18, 2021 at 19:53
  • $\begingroup$ You mean this thing, right? en.wikipedia.org/wiki/Kleene_star $\endgroup$ Commented Feb 18, 2021 at 19:55
  • 1
    $\begingroup$ this: en.wikipedia.org/wiki/Kleene_star#Kleene_plus $\endgroup$ Commented Feb 18, 2021 at 19:58
  • $\begingroup$ You should look at the first three categories of en.wikipedia.org/wiki/Substring $\endgroup$ Commented Feb 18, 2021 at 21:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.