(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 {0,1}, all strings of length 3 or less that have more 0’s than 1’s

## Expert Answer

**Solution:**

*Regular Expression:*

A regular expression defines pattern of text or set of characters which is an alphabet set ( for example {0,1} for this question) to define particular language or regular language.

*Finite State Machine:*

A finite state machine is defined by 5 tuples: ( Q, , , q_{0}, F) where Q is the set of states, is the set of input alphabet, is the transition function which maps Q X -> Q, q_{0} is the start symbol, and F is the set of final states.

**Regular Expression for the language will be:**

**001 + 100 + 010 + 00 + 0**

As mentioned in the question, in the above solution the string length is 3 for the first 3 types ( 001, 100, 010) where number of 0’s are greater than number of 1’s. The string size is less than 3 for 00 and 0 where no 1 appears to fulfill the condition.

**FSM for the above language is:**

Here Q = { q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}}

= {0,1}

q_{0} is the initial state.

F = {q_{1}, q_{2}, q_{3}}

In the above diagram, the strings 010,100, 001, 00 and 0 is accepted by the FSM( keeping the string length <= 3). A dead state q_{5} is initialized so that if the FSM is given more input which are not accepted, then the FSM goes into dead state.

*State Diagram:*