Practice Work

1

Let $S=\{x,y\}$. For each of the following, find a regular expression representing it:

1. All strings that do not contain the substring $xx$. $y^{\ast }(x\cup y^{\ast })y^{\ast }$
2. Strings that contain at least one $y$ and do not end with $xx$. $(x\cup y{)}^{\ast }(y\cup xy)$

title: Incorrect answers(?)
Use Regex equivalence checker.

2

Convert $\text{Language\_of}(1((0\cup 1{)}^{\ast }1{)}^{\ast }0)$ into a finite automata accepting it.

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle] t;
	node[shape=circle];
	init->s
	
	s->q [label=1]
	q->r [label=0]
	r->r [label=0]
	q->u [label=1]
	q->t [label=0]
	r->u [label=1]
	u->u [label=1]
}

title: Incorrect answer.