submit a .regex file with a regular expression defining the given language. you

Question

submit a .regex file with a regular expression defining the given language.

you can test it using the given link (remember to select the regex button)

Use the regular expression evaluator to test each regex: http://web.cs.ucdavis.edu/-doty automata/regex.html. Do not test them using the regular expression library of a programming language; typically these are more powerful and have many more features that are not available in the mathematical definition of regular expressions from the textbook. Only the special symbols CI are allowed, as well as "input alphabet" symbols: alphanumeric, and . and 0. even 1 odd 0 or more: x 10, 11*" r has an even number of 1's, or r has an odd number of O's, or r contains both the substrings 1101 and 00101

Explanation / Answer

First step is ...

string contains (1101) and (00101) . so place it first.

regex = (1101 | 00101)

-------------------------------------------------------------------------------------------------------------------------------------------------------

step2:

For above regex, given conditions not met (even 1's and odd 0's)

(1101 | 00101) ===> trmasformed to ===>   ( 1(11)* (00)* 1101 (11)* (00) | (11)* (00)* 00101 (11)* (00)* )

===> further reduced to ... (11)* (00)* ( 11101 | 00101) (11)* (00)*

-------------------------------------------------------------------------------------------------------------------------------------------------------------

regex file

// This DFA recognizes { x in {0,1}* | x contains strings 1101 00101 }

states = {q,q110,q1101,q00101,q0010} // 000 must contain or 111 must contain

input_alphabet = {0,1}

start_state = q // no last bit when we start

accept_states = {q,q1101,q00101} // accept if last three bits were not 000

delta =
// if we see a more than 3 1's or 3 0's then, reset
q,0 -> q;
q,1 -> q;

// until we get to three consecutive
q110,1 -> q1101;
q0010,1 -> q00101;
q0010,0 -> q0010;
q00101,0 -> q00101;
q00101,1 -> q00101;
q110,0 -> q110;
q1101,0 -> q1101;
q1101,1 -> q1101;

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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