Composing Regular Languages, DFA Equivalence and RegEx

Question 1

What does it mean if L1 union L2

Answer 1

A string is accepted if it is either L1 or L 2

Question 2

What does it mean if L1L2 (concatenation)?

Answer 2

A string is accepted if it can be split into two parts where the first part is in L1 and the second part is in L2

Question 3

What does it mean if L1*

Answer 3

Accepts any number of concatenated strings from L1

Question 4

What is L1^r

Answer 4

The reverse of L1 is accepted

Question 5

What is L1’

Answer 5

A string is accepeted if it is not in L1

Question 6

what does it mean if L1 intersection L2

Answer 6

A string is accepeted if it is in both L1 and L2

Question 7

Draw the NFA for L1 union L2

Answer 7

Question 8

Draw the NFA for L1L2

Answer 8

Question 9

Draw the NFA for L1*

Answer 9

Question 10

Draw the NFA for L1^r

Answer 10

Question 11

Draw the NFA for L1’

Answer 11

Question 12

what does b.c mean

Answer 12

the dot means a concatenation, a followed by x

Question 13

what does a + b.c mean

Answer 13

a or (b followed by c)

Question 14

what does the Σ mean in

Answer 14

the set containing the alphabet

Question 15

what is the order of precedence of these symbols

union
^*
^+
.
+

Answer 15

^+
^*
.
+
UNION

Question 16

What is the language of the regex r = (aa)^(bb)b

Answer 16

L(r) = {a^(2n)b^(2m)b : n,m >= 0}

Question 17

When is a language regular

Answer 17

If and only if a regular expression describes the language