1.3 REGULAR EXPRESSIONS (reglulegar segðir)

Question 1

What are regular expressions?

Answer 1

we can use the regular operations to build up expressions describing languages, which are called regular expressions. An example is:
(0∪1)0∗.

Question 2

Σ∗ describes

Answer 2

the language consisting of all strings over that alphabet.

Question 3

Σ∗1 is ?

Answer 3

the language that contains all strings that end in a 1.

Question 4

Which operations are done first in regex?

Answer 4

The star operation is done first,
followed by concatenation,
and finally union,
unless parentheses change the usual order.

Question 5

Formal definition of a regular expession

Answer 5

Say that R is a regular expression if R is
1. a for some a in the alphabet Σ,
2. ε,
3. ∅,
4. (R1 ∪ R2), where R1 and R2 are regular expressions,
5. (R1 ◦ R2), where R1 and R2 are regular expressions, or
6. (R1∗), where R1 is a regular expression.

Question 6

Don’t confuse the regular expressions ε and ∅. What is the different?

Answer 6

The expression ε represents the language containing a single string—namely, the empty string—whereas ∅ represents the language that doesn’t contain any strings.

Question 7

0∗10∗

Answer 7

{w| w contains a single 1}.

Question 8

Σ∗1Σ∗

Answer 8

{w| w has at least one 1}.

Question 9

Σ∗001Σ∗

Answer 9

{w| w contains the string 001 as a substring}.

Question 10

1∗(01+)∗

Answer 10

{w| every 0 in w is followed by at least one 1}.

Question 11

(ΣΣ)∗

Answer 11

{w| w is a string of even length}.

Question 12

(ΣΣΣ)∗

Answer 12

{w| the length of w is a multiple of 3}.

Question 13

01 ∪ 10

Answer 13

{01, 10}.

Question 14

0Σ∗0 ∪ 1Σ∗1 ∪ 0 ∪ 1

Answer 14

{w| w starts and ends with the same symbol}.

Question 15

(0∪ε)1∗

Answer 15

01∗ ∪1∗.

The expression 0 ∪ ε describes the language {0, ε}, so the concatenation operation adds either 0 or ε before every string in 1∗ .

Question 16

(0∪ ε)(1∪ ε)

Answer 16

{ε,0,1,01}.

Question 17

1∗∅

Answer 17

∅.

Concatenating the empty set to any set yields the empty set.

Question 18

∅∗

Answer 18

{ε}.

The star operation puts together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, giving only the empty string.

Question 19

A language is regular if and only if some regular expression describes it.

Answer 19

Say that we have a regular expression R describing some lan- guage A. We show how to convert R into an NFA recognizing A. By Corol- lary 1.40, if an NFA recognizes A then A is regular.

Question 20

We convert the regular expression (ab ∪ a)∗ to an NFA in a sequence of stages.

Question 21

If a language is regular, then it is described by a regular expression.

Answer 21

PROOF IDEA We need to show that if a language A is regular, a regular expression describes it. Because A is regular, it is accepted by a DFA. We describe a procedure for converting DFAs into equivalent regular expressions.

Question 22

How do we convert regex to DFA ?

Answer 22

We break this procedure into two parts, using a new type of finite automaton called a generalized nondeterministic finite automaton, GNFA. First we show how to convert DFAs into GNFAs, and then GNFAs into regular expressions.

Question 23

What are Generalized nondeterministic finite automata?

Answer 23

Generalized nondeterministic finite automata are simply nondeterministic fi- nite automata wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet or ε.

Question 24

For convenience, we require that GNFAs always have a special form that meets the following conditions.

Answer 24

The start state has transition arrows going to every other state but no arrows coming in from any other state.

There is only a single accept state, and it has arrows coming in from every other state but no arrows going to any other state. Furthermore, the accept state is not the same as the start state.

Except for the start and accept states, one arrow goes from every state to every other state and also from each state to itself.

Question 25

We can easily convert a DFA into a GNFA in the special form. How ?

Answer 25

We simply add a new start state with an ε arrow to the old start state and a new accept state with ε arrows from the old accept states. If any arrows have multiple labels (or if there are multiple arrows going between the same two states in the same direction), we replace each with a single arrow whose label is the union of the previous labels. Finally, we add arrows labeled ∅ between states that had no arrows.

Question 26

A generalized nondeterministic finite automaton is a 5-tuple, (Q, Σ, δ, qstart, qaccept), where

Answer 26

1. Q is the finite set of states,
2. Σ is the input alphabet,
3. δ: (Q − {qaccept}) × (Q − {qstart})−→R is the transition function,
4. qstart is the start state, and
5. qaccept is the accept state.