296 views
0 votes
0 votes
What is the language generated by  0(0+1)*(0+1)+ϵ+1(0+1)*1

1 Answer

Best answer
2 votes
2 votes

Let's analyze the given regular expression: $0(0+1)^*(0+1)+ϵ+1(0+1)^*1$

Breaking it into 3 parts:

$0(0+1)^*(0+1)\ $: This consists of strings that start with a 0 and can end with either a 0 or a 1. In between we can have any arbitrary length of string in {0, 1} (i.e $(0+1)^*$). The minimum length strings are 01 and 00.

$\epsilon \ $: This is the empty string. Hence the language contains empty string. 

$1(0+1)^*1\ $: This represents the set of strings starting with a 1 and ending with a 1, with anything in between. Here the minimum length string is 11. 

So, the language contains strings from all these parts. 

"All the strings including empty string of length >=2, if started with 1 should end with 1"

 =   All strings of length greater than or equal to 2 which start with 1 and end with a 1 .

   + All strings of length greater or equal to 2 starting with a 0.

   + epsilon (empty string).

selected by

Related questions

0 votes
0 votes
1 answer
1
practicalmetal asked Mar 25, 2023
379 views
The solution to $X = r +Xs$ by Arden’s Lemma when s has ϵa) an infinite number of solutionsb) a finite number of solutionsc) is always uniqued) none
1 votes
1 votes
1 answer
2
atulcse asked Jan 28, 2022
487 views
Which of the following languages is/are regular?
5 votes
5 votes
3 answers
3
Hirak asked May 25, 2019
1,820 views
Consider the following statements:$S_1:\{(a^n)^m|n\leq m\geq0\}$$S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $Which of the following is regular?$S_1$ only$S_2...