Write regular expressions which describe the following languages. Remember your answers must only use symbols from definition

computer science

Description

Write regular expressions which describe the following languages. Remember your answers must only use symbols from definition 3.5, i.e., letters from the alphabet (which is {0,1}{0,1} in each case), (( ,)), εε, ∅∅, ∪∪, and ∗∗. 


Try to write the regular expressions from scratch rather than converting equivalent NFAs. If you decide to do the latter, make sure your result is as simple as possible. 


1. {w∈{0,1}∗|w ends with 101}{w∈{0,1}∗|w ends with 101} 


2. {w∈{0,1}∗|w starts with 10 and ends with 1}{w∈{0,1}∗|w starts with 10 and ends with 1} 


3. {w∈{0,1}∗|w contains the substring 01}{w∈{0,1}∗|w contains the substring 01} 


4. {w∈{0,1}∗|w does not contain the substring 01}{w∈{0,1}∗|w does not contain the substring 01} 


5. {w∈{0,1}∗|w contains exactly one occurrence of 01}{w∈{0,1}∗|w contains exactly one occurrence of 01} 


6. {w∈{0,1}∗|w has a 1 in the third position}{w∈{0,1}∗|w has a 1 in the third position} 


7. {w∈{0,1}∗|w has even length}{w∈{0,1}∗|w has even length} 


8. {w∈{0,1}∗|w has an odd number of 0}{w∈{0,1}∗|w has an odd number of 0} 


9. {w∈{0,1}∗|w has an odd number of 0’s or an even number of 1’s}{w∈{0,1}∗|w has an odd number of 0’s or an even number of 1’s} 


Question 4 

Convert the following regular expressions into nondeterministic finite automata using the method shown in the videos. Represent the automata in the form of diagrams. 


You should simplify your models as you build them – for example you may remove redundant states and combine states that are linked with epsilon transitions, but make sure the language is unchanged. 


1. (aba∪bb∪ba)∗(aba∪bb∪ba)∗ 


2. ab(a∪b)∗a(a∪b)∗ab(a∪b)∗a(a∪b)∗ 


3. a(bb)∗∪aba(bb)∗∪ab


4. b∗a∗(ba∪b∗)b∗a∗(ba∪b∗)


Related Questions in computer science category


Disclaimer
The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.