So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be in the language. I think the language w1w2w3 is just similar to {0,1}* . I can create a NFA for {0,1}* , so that is why the language is regular. w1w2w3 is just like a concatenation of w1,w2,w3 but all of them are {0,1}* so the NFA for the language {0,1}* is also the NFA that accepts the language A2. Is my thinking so far correct? Will the NFA accept the language?

enter image description here


1 Answer 1

  1. If you think the language is regular, there is no point using the pumping lemma. It is used to prove that some languages are NOT regular.
  2. The sentence "$\{0,1\}^*$ can represent the NFA for the language" makes absolutely no sense.
  3. Your language is equal to $\{0,1\}^*$ (you can choose any $w_1$, and $w_2 = w_3 = \varepsilon$).
  • $\begingroup$ Thank you for the reply. For 2) I wanted to say the NFA that represents the {0,1}* not the other way around, I edited it. So, since per 3) the language A2 is equal to the language {0,1}*, the above NFA accepts the language A2. Am I right in saying that since w1,w2,w3 all belong to {0,1}*, then the resulting string w1w2w3 also is in {0,1}*? $\endgroup$
    – Crypton99
    Oct 19, 2023 at 21:53
  • $\begingroup$ Also, I was not sure for 1), I tried pumping lemma to verify if I can prove it not regular but I could not find a string to do so. I guess where I am confused is: you say choose w1 and w2 = w3 = ε, then language is equal to {0,1}*, but say for an irregular language w1w2w1, can't I do the same and get the result language is equal to {0,1}*? But that is not true. So I am making a mistake somewhere (in choosing the values of w1,w2). $\endgroup$
    – Crypton99
    Oct 19, 2023 at 22:01
  • $\begingroup$ For your first comment: there were no NFA in your initial post. In your edit, this is in fact a DFA, and it does not have an initial state, so it recognizes the empty language. For your second comment: you cannot do the same thing with $\{w_1w_2w_2\mid w_1, w_2\in \{0,1\}^*\}$, because if you choose $w_1$ to be any non-empty word, you cannot choose it to be the empty word at the same time. $\endgroup$
    – Nathaniel
    Oct 20, 2023 at 5:00
  • $\begingroup$ Thanks @Nathaniel $\endgroup$
    – Crypton99
    Oct 26, 2023 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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