USA: +1 (725) 712-1730 
Sign in
For alphabet {x,y,z}, all strings that contain xyx or zyz
(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.
Expert Answer
1. The first two lines are the regular expression of the language. They are the same but the second one is the minified version of the first one. Here + means or operator(any one of those) and * means Kleen’s closure (a* means null or a or aa or aaa till infinite length strings). So in the beginning or the end could be any combinations of x, y or z but in there somewhere there must xyx or zyz. This would include all the strings irrespective of where zyz or xyx might be.
2. The input alphabets are x, y and z. There are 6 states as shown in the diagram. There starting state is the state 1 where as the final/accepting state is the state 6. The transition table is:
State x y z
1 2 1 4
2 2 3 4
3 6 1 4
4 2 5 4
5 2 1 6
6 6 6 6
