CODEWITHSUNDEEP
computation-theory
JAMIL AHMAD
JAMIL AHMAD

Reputation: 11

Write regular expressions for the following languages over the alphabet

Write regular expressions for the following languages over the alphabet ∑ = {0, 1}:

  1. Language of all strings which do not end with 11.
  2. Language of all strings which do not contain the substring 01. also Draw Finite Automaton for each of the above described languages.

Upvotes: 1

Views: 2129

Answers (1)

Patrick87
Patrick87

Reputation: 28312

A regular expression for the first one is e + 0 + 1 + S* (00 + 01 + 10) where e is the empty string, S is the alphabet, * is the Kleene closure, + is union. This works because the language can be divided into strings of length less than two (e + 0 + 1) and strings of length at least two which do not end with 11 (this leaves endings 00, 01, and 10).

A regular expression for the second language is 1*0*. Note that we must put any 1s on the left of all 0s to avoid the substring 01, but we can have as many as either as we like.

A DFA for the first one would look like

q    e    q'
q0   0    q0
q0   1    q1
q1   0    q0
q1   1    q2
q2   0    q0
q2   1    q2

State q0 is initial, q0 and q1 are accepting. In state q0, you either just started or last saw a zero; your last symbol wasn't 1. In state q1, your last symbol was 1, but your second to last symbol wasn't. In state q2, you have seen two 1s in a row.

A DFA for the second would look like:

q    e    q'
q0   0    q1
q0   1    q0
q1   0    q1
q1   1    q2
q2   0    q2
q2   1    q2

q0 is the initial state, and q0 and q1 are accepting. q0 reads all the 0s, q1 reads all the 1s, and q2 happens if we see a 0 after we have seen a 1.

Upvotes: 0

Related Questions