Week 1 - Regular Expressions

Question 1

List the 3 regular operations?

Answer 1

Union
Concatenation
Star

Question 2

What is a union operation in terms of sets?

Answer 2

Joining two or more sets together into one larger set containing the items from each set.
e.g.
A = {good, bad} and B {boy, girl}
A∪B = {good, bad, boy, girl}

Question 3

What is a concatenation operation in terms of sets?

Answer 3

Concatentating the items from one set with each of the items from a second set.
e.g.
A = {good, bad} and B {boy, girl}
A∘B = {goodboy, goodgirl, badboy, badgirl}

Question 4

What is a star operation in terms of sets?

Answer 4

When you get all possible concatenations of the words from a finite set. This will include Ɛ. If the set isn’t empty, then the star of that set is infinite.
e.g.
A = {good, bad}
A* = {Ɛ, good, bad, goodgood, bad, badbad, goodbad, badgood, goodgoodgood, …}

Question 5

What happens if you concatenate a language/set with an empty set?

Answer 5

You get an empty set.

Question 6

What happens if you concatenate a language/set with a set containing only Ɛ?

Answer 6

You get the original language/set back.

Question 7

What happens if you star an empty set?

Answer 7

You get a set containing only Ɛ.

Question 8

What happens if you star a set containing only Ɛ?

Answer 8

You get a set containing only Ɛ.

Question 9

TRUE OR FALSE: A language created by the union of two seperate regular languages is also a regular language.

Answer 9

TRUE, there is always a FA that will recognise a union of two regular languages. This machine can be represented by a machine containing an initial state with two Ɛ transitions, one to the machine of the first language of the union and one to the second.

Question 10

What is the algorithm for constructing an NFA that accepts the Language L(M1)∪L(M2)?
Assume M1 is the machine that accepts L(M1) and M2 is the machine that accepts L(M2).

Answer 10

You create an initial state for the new machine, with two Ɛ transitions, one that goes to the initial state of M1 and one that goes to the initial state of M2. These two states are no longer the initial states. You must rename the states of M2 (or M1) so that the states of those machines are not the same. Follow the convention 1->1prime1, 2->2prime1 etc.. The final states of the new machine are the final states of both M1 and M2.

Question 11

TRUE OR FALSE: The language created through concatenation of two regular languages is also a regular language?

Answer 11

TRUE.

Question 12

What is the algorithm for constructing the NFA that accepts the language L(M1)∘L(M2)? Assume M1 is the machine that accepts L(M1) and M2 is the machine that accepts L(M2).

Answer 12

The initial state of the new machine will be the initial state of M1, and the final state(s) of M1 will now have Ɛ transition(s) to go to the initial state of M2. The final states of this new machine will be the final states of M2. You must rename the states of M2 (or M1) so that the states of the machines are not the same. Follow the convention 1->1prime1, 2->2prime1 etc..
Any concatenation of a word from L(M1) and L(M2) will follow the start of the new machine through the M1 section, then go to the M2 section and follow through that and get to the end.

Question 13

TRUE OR FALSE: The language that is created through a star operation of a regular language is also a regular language?

Answer 13

TRUE.

Question 14

What is the algorithm for constructing the NFA that accepts the language L(M)*? Assume M is the machine that accepts L(M).

Answer 14

Add an initial state, which has an Ɛ transition to the old initial state of M. Add transitions from all the final state(s) of M that go the the old initial state of M. Make sure that the new initial state does not have the same name as a state in M so that they can be distinct. Normally you can name it 0.
Any possible concatenation of words from a language will go through this new machine, get to the end of the machine when it reads a substring word from that concatenation, and then loop back to the start and read through the next substring word until it has read through the entire concatenated string.

Question 15

What is a regular expression?

Answer 15

An expression that is either:
o A symbol contained in an alphabet.
o Ɛ
o an empty set
o R1∪R2 where R1 and R2 are both regular expressions
o R1∘R2 where R1 and R2 are both regular expressions
o R1* where R1 is a regular expression

Question 16

What is L(R)?

Answer 16

The language described by a regular expression R.

Question 17

What is an easier way to write L1∘L2?

Answer 17

L1L2

Question 18

What does R+ mean?

Answer 18

RR*

Question 19

In what order do you do the regular operations in a regular expression?

Answer 19

Star, then concatenation, then union.

Question 20

Describe the language represented by 010 in computational terms.

Answer 20

{w∈{0, 1}* / w = 0…0#length m# 1 0…0#length n#, m, n >= 0}

Question 21

Describe the language represented by 0*10+ in computational terms.

Answer 21

{w∈{0, 1}* / w = 0…0#length m# 1 0…0#length n#, m>=0, n >= 1}

Question 22

TRUE OR FALSE: You can create an NFA from any regular expression.

Answer 22

TRUE, its called REGULAR expression for a reason.

Question 23

How do you create an NFA that recognises a regular expression?

Answer 23

For all languages used in the regular expression, construct a NFA. Then construct an NFA for each use of operation of the languages in the expression. Then construct an NFA for each use of operation of the regular languages created from operations in the expression. And so on until you have finished the regular expression.
e.g.
Assuming a and b are regular languages, the expression is (ab∪a)*
Create NFA for a and b. Then create an NFA for the concatentation of ab. Then create an NFA for the union of ab∪a using the NFA of ab. Then create an NFA from the * operation of the previous NFA.