For each of the languages L1, L2, L3, L4 described below: (1) Write a regular ex

Question

For each of the languages L1, L2, L3, L4 described below: (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. L1: For alphabet {a, b}, all strings that contain an odd number of a's and exactly one b. L2: For alphabet {0, 1}, all strings of length 3 or less that have more 0's than 1's. L3: For alphabet {x, y, z}, all strings that contain xyx or zyz. L4: For alphabet {p, q, r}, all strings that contain the substring rqr or end with pp.

Explanation / Answer

Regular Expression:

L1 {a,b}, odd number of a’s and exactly one b.

There are 2 cases:

Putting together

(a, a)* b (aa)* a + (aa)*ab(aa)*

L2: {0,1}, length <=3 or more than 1’s.

There can be following cases:

Putting together

L3 : = {x,y,z} contains xyz or zyz

There can be following cases:

Putting together

(x+y+z)* (xyz+zyz)+ (x+y+z)*

L4: = {p,q,r} either substituting rqr or end with pp

There can be following cases:

Putting together

(p + q + r)* (rqr(p+q+r)*+pp)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.