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!
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Hm. What does "there is no pattern" mean? $\endgroup$– Daniel WagnerCommented Jul 24, 2021 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$– JeffreyCommented Jul 24, 2021 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$– Anshika SinghCommented Jul 25, 2021 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$– Anshika SinghCommented Jul 25, 2021 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$– Daniel WagnerCommented Jul 25, 2021 at 14:37
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
0
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)^+.$$
$\begingroup$
$\endgroup$
0
The language is regular and a possible regular expression for $L$ is $(a\mid b)^* (a \mid b) (a \mid b)^* = (a \mid b)^+$.
