(1)

Write a regular expression for the language.

(2)

Define a finite state machine (FSM) that recognizes words in the language (input alphabet, states, start state, state transition table, and accept states). Include a state digraph for the FSM.

A: For alphabet {x,y,z}, all strings that contain xyx or zyz.

## Expert Answer

**Question (a):**

A regular expression is a pattern of text to define regular language.

For this given question the regular expression is:

**x ^{*}y^{*}z^{*}(xyx + zyz )x^{*}y^{*}z^{*}**

Here two operations are used:

**Concatenation**to indicate one alphabet*followed by*another making a sentence.**Union (+)**on a regular expression a + b indicates*either**a or b.*

Another operation * ( also known as kleene closure) is used to denote repetition for zero (0) or more times.

Therefore the minimum string generated from the above regular expression is **x followed by y followed byz or z followed by y followed by z** when the there is no repetition for either of x or y or z.

**Finite State Automaton:**

A finite state automaton is a 5 tuple ( Q, , , q_{0} , F) where Q is the set of states, is the set of input alphabt, is a transition function which maps Q X -> Q ( for Deterministic Finite state Automaton) or Q X -> 2^{Q} ( for Non-deterministic Finite state Automaton), q_{0} is the initial state and F is the set of final states.

*Question (2):*

*FSM:*

Here, NFA is used where Q = { q_{0} , q_{1} , q_{2} , q_{3}, q_{4,} q_{5}}

= {x, y, z}

q_{0} is the initial state

F=q_{3}

and the transition function is defined in the following table:

*State Diagram:*