Question

Given R=1∗0+1+0+1+and S=(1+0+ )∗1+ where Σ={0,1} - Give an example of a string that is neither in the language of R nor in S.

a) Give an example of a string that is in the language of S but not R.
b) Give an example of a string that is in the language of R but not S.
c) Give an example of a string that is in the language of R and S.
d) Design a regular expression that accepts the language of all binary strings with no occurrences of 111

Answer 1

The requested strings and patterns are found by analyzing the given regular expressions R and S. A string like '111' is in S but not in R, '1010' is in R but not S, '101' is in both, and a regular expression for no '111' occurrences is identified.

Step-by-step explanation:

Regular expressions R and S describe the patterns in a set of strings over the binary alphabet Σ={0,1}. To address the questions, we need to understand each expression:

1. R is 1*0+1+0+1+, which means strings with multiple ones, possibly none, followed by at least one zero and at least one pattern of alternating ones and zeros.
2. S is (1+0+)*1+, which consists of any number, including zero, of sequences containing at least one '1' or at least one '0', ending with one or more ones.

a) String in S but not in R:

'111' is in S as it ends in one or more ones but not in R because R requires a zero to be present.

b) String in R but not in S:

'1010' is in R but not in S because S requires the string to end with one or more ones.

c) String in R and S:

'101' satisfies both R and S as it alternates after a series of ones and ends with one or more ones.

d) Regular expression for no occurrence of '111':

A regular expression that accepts all binary strings with no occurrences of '111' can be characterized as '(0|10*1)*'. This pattern means any number of sequences starting with a zero or a one followed by any number of zeros then a one, not allowing three consecutive ones.