Foundations of Computation | Assignment

Running head: FOUNDATIONS OF COMPUTATION
Foundations of Computation
Name of the Student
Name of the University
Author’s Note

1
FOUNDATIONS OF COMPUTATION
Answer to Question 1:
1. {w∈{a,b}∗|w has neither aa nor bb as a substring }{w∈{a,b}∗|w has neither aa nor bb as a
substring }
2. {w∈{a,b}∗|each a in w is immediately preceded by a b}{w∈{a,b}∗|each a in w is immediately
preceded by a b}
3. {w∈{a,b}∗|w has baba as a substring}{w∈{a,b}∗|w has baba as a substring}

2
FOUNDATIONS OF COMPUTATION
4. {w∈{a,b}∗|w has an odd number of a’s and an even number of b’s}{w∈{a,b}∗|w has an odd
number of a’s and an even number of b’s}
5. {w∈{a,b}∗|w has both ab and ba as substrings }{w∈{a,b}∗|w has both ab and ba as
substrings } Note: the string abaaba should be accepted.