The language given is $L = \{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$. Is this language regular or not?

Since there is no pattern, so it should be non-regular?

Kindly help!

  • 2
    $\begingroup$ Hm. What does "there is no pattern" mean? $\endgroup$ Jul 24 at 21:34
  • 5
    $\begingroup$ "Since there is no pattern, so it should be non-regular?" This is problematic, as a statement. it seems you misunderstand something. please elaborate $\endgroup$
    – Jeffrey
    Jul 24 at 22:49
  • $\begingroup$ All the regular languages are finite and thus, can be represented using deterministic or non-deterministic finite automata. For that, the language should have some sort of pattern so that the language can be represented as a DFA/NFA or as a regular expression. @DanielWagner $\endgroup$ Jul 25 at 7:18
  • $\begingroup$ @Jeffrey Any regular language, that is to be represented on a DFA/NFA has some sort of loop, and that is what I mean by pattern here. For example L=set of strings ending with a: can be represented as a DFA by having a self loop of a on the final state.. $\endgroup$ Jul 25 at 7:31
  • 1
    $\begingroup$ Well it certainly isn't the case that all the regular languages are finite. The simplest DFA I can think of is a single node, marked final, with self edges for each letter in the alphabet; the set of strings this accepts is infinite. (Though perhaps this just a terminology issue; when you say "language" do you mean "set of strings"? That is what other people here will assume you mean.) As for "the language should have some sort of pattern", well... if you can write something down that defines it, as you have done here, isn't that a pattern? $\endgroup$ Jul 25 at 14:37

It's regular because your language is equal to (suppose $\Sigma=\{a,b\}$) $$L=\Sigma^*\Sigma\Sigma^*$$ $$=\Sigma^+.$$ So we can represent $L$ by regular expression: $$(a+b)^*(a+b)(a+b)^*$$ $$=(a+b)^+.$$


The language is regular and a possible regular expression for $L$ is $(a\mid b)^* (a \mid b) (a \mid b)^* = (a \mid b)^+$.


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.