8 Determine if $L$ in $P$

Input: Sets $A_{1}, . . ., A_{n}$ , and a number $k$ .
Question: do there exist $k$ mutually disjoint sets $A_{i 1}, . . ., A_{i k}$ not in $P$
Input: Sets $A_{1}, . . ., A_{n}$ .
Question: do there exist 3 mutually disjoint sets $A_{i}, A_{j}, A_{k}$ in $P$
Input: Sets $A_{1}, . . ., A_{n}$ , and a number $k$ .
Question: do there exist $k$ sets such that $A_{i 1}, . . ., A_{i k}$ such that $A_{i} \cap A_{j} \neq \emptyset$ not in $P$
Input: a CNF formula $ψ$ with at most 50 variables.
Question: does there exist an assignment that satisfies $ψ$ in $P$
Input: a CNF formula $ψ$ with at most 50 clauses.
Question: does there exist an assignment that satisfies $ψ$ in $P$
Input: a 3CNF formula $ψ$ with even number of variables.
Question: does there exist an assignment that satisfies $ψ$ and gives $T r u e$ for exactly one half of the variables? not in $P$
Input: undirected graph $G$ , a number $k$ .
Question: does there exist in $G$ a clique of size at least $k$ or an independent set of size at least $k$ ? not in $P$

Resulting regular expression:

$L^{'} = {0^{i} 1^{j} : i, j \geq 0 and \exists w \in L s . t | w | = i + j}$ is regular if $L$ regular T. built NFA $Q \times {0, 1}$ , $δ^{'} ((q, 0), 0) = {(δ (q, σ), 0) : σ \in Σ^{*}} . δ^{'} ((q, 0), ϵ) = {(δ (q, 1), σ) : σ \in Σ^{*}}$
$L^{'} = {0^{i} 1^{j} : i, j \geq 0 and \exists w \in L s . t | w | = | i - j |}$ is regular if $L$ regular F. take $L = ϵ$ r = r1* r2(r4+r3r1*r2)* where: r1: initial → initial r2: initial → accepting r3: accepting → initial r4: accepting → accepting

L_{2} = {y : \exists x, z s . t . | x | = | z | a n d x y z \in L}

(Example) is regular.onsider some DFA for $L$ . For every $n \geq 0$ , let $A_{n}$ be the set of states $s$ such that there is *some* word of length $n$ which leads the DFA from the initial state to $s$ . Let $B_{n}$ be the set of states $t$ such that there is *some* word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s, t$ , let $R_{s, t}$ be the (regular) set of words leading the DFA from $s$ to $t$ . We have

L_{2} = ⋃_{n \geq 0} ⋃_{\begin{matrix} s \in A_{n} \\ t \in B_{n} \end{matrix}} R_{s, t} .

Since there are only finitely many possibilities for $s, t$ , the union is in fact finite, and so regular.

8.1 Examples

$L = {⟨ M ⟩ : M$ is a TM and $| L (M) | > 10} \in RE / R$
$L = {M : ⟨ M ⟩ is a TM that accepts 1 but does not accept 0} \in \overset{―}{RE \cup co- RE}$
$L = {⟨ M_{1}, M_{2} ⟩ : M_{1}, M_{2}$ are TMs and $L (M_{1}) \cap L (M_{2}) = \emptyset} \in co- RE / R$
$L = {⟨ M_{1}, M_{2} ⟩ : M_{1}, M_{2}$ are TMs and $L (M_{1}) \subseteq L (M_{2})} \in \overset{―}{RE \cup co- RE}$
$L_{n} = {w 0 w_{n} | w \in {0, 1}^{*} \land w_{n} \in {0, 1}^{n - 1}}$ is Regular
$L_{1} = {w : # a (w) \geq # b (w)} over Σ = {a, b, c}$ $L_{1}$ is not regular
$L_{2} = {w : | w | \in N_{e v e n} \land w = w^{R})} over$ $L_{2}$ is not regular
$L_{4} = {w : | w | \in N s.t | w | = n^{3}} over$ $L_{4}$ is not regular
$L = {⟨ M ⟩ | M$ is a TM and there exists an input on which M halts in less than $| M |$ steps $} \in R$
$L = {⟨ M ⟩ | M$ is a TM and $| L (M) | \leq 3} \in$ co-RE reduce $\overset{―}{H A L T}$ . idea copies M and x to its tape, and runs M on x; it accepts if M halts on x.
$L = {⟨ M ⟩ | M$ M is a TM and $| L (M) | \geq 3} \in$ RE reduce $H A L T$ . It erases w, puts M and x on its tape, and runs M on x and accepts if M halts on x.
$L = {⟨ M ⟩ | M$ is a TM that accepts all even numbers $} \in$ not RE
$L = {⟨ M ⟩ | M$ is a TM and $L (M)$ is finite $} \in$ not RE
$L = {⟨ M ⟩ | M$ is a TM and $L (M)$ is infinite $} \in$ not RE
$L = {⟨ M ⟩ |$ is a TM and $L (M)$ is countable $} \in$ R This is the language of all TM’s, since there are no uncountable languages ( finite alphabets and finite-length strings).
$L = {⟨ M ⟩ | M$ is a TM and $L (M)$ is uncountable $} \in$ R This is the empty set
$L = {⟨ M_{1}, M_{2} ⟩ |$ are TM’s and $ϵ \in L (M_{1}) \cup L (M_{2})} \in$ RE. reduce HALT s.t $⟨ M, x ⟩ \mapsto ⟨ M^{'}, M^{'} ⟩$ $⟨ M, x ⟩$ halts on $x \Rightarrow M^{'}$ accepts all strings, and in particular it accepts $ϵ \Rightarrow ϵ \in L (M^{'}) \cap L (M^{'})$ .
$L = {⟨ M_{1}, M_{2} ⟩ |$ are TM’s and $ϵ \in L (M_{1}) \cap L (M_{2})} \in$ RE.
$L = {⟨ M_{1}, M_{2} ⟩ |$ are TM’s and $ϵ \in L (M_{1}) / L (M_{2})} \in$ not RE.
$\overset{―}{H A L T} (M, x) \mapsto (M_{1}, M_{2}) .$ s.t $L (M_{1}) = Σ^{*}$
$L = {⟨ M ⟩ | M$ is a TM. and $M_{0}$ halt on all input, and $M_{0} \in L (M)} \in$ RE using Rice $C = {L \in R E : M_{0} \in L}$
$L = {⟨ M ⟩ | M$ is a TM. and $M_{0}$ halt on all input, and $M \in L (M_{0})} \in$ R
$L = {⟨ M ⟩ | M$ is a TM. and $x$ is str and there exists a TM, $M^{'}$ , such that $M \notin L (M^{'}) \cap L (M)} \in$ R
$L = {⟨ M ⟩ | M$ is a TM. , and there exists an input whose length is less than 100, on which M halts $} \in .$ RE
$L = {⟨ k, x, M_{1}, \dots M_{k} ⟩ | \forall i M$ is a TM, and at least $k / 2$ TM’s of halt on x $} \in .$ RE its $\emptyset$ reduce $H A L T (M, X) \mapsto (2, x, M, M^{'})$
$L = {⟨ M ⟩ | M$ is a TM and M halts on all palindromes . $} \in .$ not RE . $\overset{―}{H A L T} (M, w) \mapsto M^{'}$ on input x works as follows: $M^{'}$ runs M on w for $| x |$ steps: if M halts on w within $| x |$ steps, reject, otherwise accept.(if $x$ is polindrome)
$L = {⟨ M ⟩ | M$ is a TM and $L (M) \cap {a^{2^{n}}}}$ is empty. $} \in .$ not RE $\overset{―}{H A L T} (M, w) \mapsto M^{'}$ $M^{'}$ on input x: erase x, and run M on w. If M halts on w then $M^{'}$ accepts.
$L = {⟨ M ⟩ | M$ is a TM that halts on all inputs and $L (M) = L^{'}$ for some undecidable language $L^{'}$ . $} \in .$ R
$L = {⟨ M ⟩ | M$ is a TM and M accepts (at least) two strings of different lengths . $} \in .$ RE
$L = {⟨ M ⟩ | M$ M is a TM such that both $L (M)$ and $\overset{―}{L (M)}$ are infinite . $} \in .$ not RE M’ on input x works as follows: if x is of odd length, accept. if x is of even length, run M on w. If M halts, accept.
$(M, w) \in \overset{―}{H A L T} \Rightarrow M$ does not halt on $w \Rightarrow M^{'}$ accept all odd length str and reject all even. $\Rightarrow L (M)$ contain even-length strings, $| L | = inf$
$L = {⟨ M ⟩ | M$ is a TM, and $| L (M) |$ is prime. $} \in .$ not RE $M^{'}$ on input x: if x is one of the first three strings (in lexicographic order) of $Σ *$ , then accept. Otherwise, run M on w. If M halts on w, and x is the 4 th string in $Σ *$ accept; otherwise, reject.
$L = {⟨ M ⟩ | M$ and exists $x$ s.t for every $y \in L (M), x y \notin L (M) .} \in .$ not RE $M^{'}$ on input x: it runs M on w; if M halts on w, $M^{'}$ accepts.
$L = {⟨ M ⟩ | M$ and exists $x, y$ s.t for every $y \in L (M), y \notin L (M) .} \in .$ Recursive (the language of all Turing machines)
$L = {⟨ M ⟩ | M$ is TM and exists $M^{'}$ s.t $M \neq M^{'}$ and $L (M) = L (M^{'}) .} \in .$ Recursive(the language of all Turing machines)
$L = {⟨ M_{1}, M_{2} ⟩ | M$ and $L (M_{1}) \leq_{m} L (M_{2})}$ not RE $\overset{―}{H T} (M, w) = ⟨ M_{1}, M_{2} ⟩ .$ s.t $L (M_{2}) = \emptyset$ . $M_{1}$ on input $y$ : run M on $w$ if M halts, check whether y is of the form $⟨ M^{'}, z ⟩$ where $M^{'}$ is TM and z is str. if so run $M^{'}$ on z. if $M^{'}$ halts, $M_{1}$ accept . hence (1)if $(M, w) \in \overset{―}{H T} \Rightarrow L (M_{1}) = \emptyset$ (2) otherwize then $L (M_{1}) = H A L T$
$L = {⟨ M_{1}, M_{2} ⟩ | M$ M does not accept any string w such that 001 is a prefix of $w}$ not RE
$L = {⟨ M ⟩ | M$ M does not accept any string w s x is a prefix of $w}$ not RE
$L = {⟨ M ⟩ | M$ x is prefix of $M}$ Recurcive
$L = {⟨ M_{1}, M_{2}, M_{3} ⟩ | L (M_{1}) = L (M_{2}) \cup L (m_{3})}$ not RE
$L = {⟨ M_{1}, M_{2}, M_{3} ⟩ | L (M_{1}) \subseteq L (M_{2}) \cup L (m_{3})}$ not RE M1 on x: runs M on w; if M halts, M1 accepts.M2 on y: reject. M3 on z: reject.
$L = {⟨ M_{1} ⟩$ there exist two TM’s M2 and M3 such that $| L (M_{1}) \subseteq L (M_{2}) \cup L (m_{3})}$ Recursive
$L = {⟨ M, w ⟩$ M is a TM that accepts w using at most $2^{|} w |$ squares of its tape $}$ Recursive Let m be the number of states in M, and k be the size of the alphabet that M uses, and $r = | w |$ if M uses at most $2^{r}$ squares of its tape, then there are at most $a = m k^{2^{r}} 2^{r}$ configurations.If M runs on w for more than $a$ steps, and does not use more than $2^{r}$ squares of its tape, then M must be in the one configuration at least twice.
$M^{'}$ runs M on w for at most a + 1 steps.If M accepts w within a steps with using at most $2^{r}$ squares, $m^{'}$ halts and accepts
Wich one is False for sure $D T I M E [n^{2}] = L$ $P = N P R L \in P$
Wich one we dont know if it close under klee star $L$ $P N P E X P$
Let $f$ be computable with circut size $| S |$ we can construct circuit size $O (S)$ with only AND,NOT gate for sure.
$L = {G | G is an undirected graph that contains no odd length cycle} \in R L, N L$ (mybe)
$L = {G, 1^{k} | G is an undirected with exactly k triangles} \in L$
$L = {ψ$ is ( always true) $} \in C o - N P$ complete
$L = {G, k | G is an undirected with exactly k diffrent SCC} \in S P A C E (\log^{2} n), P$
If we find that $S = {G, s, t dont have path between s and t} \in L$ then $L = C o - N L$
${⟨ G, s, t ⟩$

G is an directed graph, and the shortest patch between s,t $i s a t least s i z e$ |V|/2 }NL ${⟨ G, s, t ⟩$ G is an directed graph, and exsit patch between s,t $excatliy s i z e$ |V|/2 }NPC If $NTIME (n^{100}) \subseteq TIME (n^{1000})$ then $P = N P, E X P = N E X P, NSPACE (n^{50}) \subseteq SPACE (n^{500})$ $E X A C T 3 S A T = {φ \in 3 S A T :$ every clause of ϕ $h a s e x a c t l y 3 d i s t i n c t v a r i a b l e s$ } is NPC $L_{2} = {⟨ M, 1^{n} ⟩ : M is a TM and there exists a string that M accepts in n steps}$ is NPC $L = {x y z : x y^{R} z \in L}$ is regular if $L$ Recursive $L = {x y \in Σ^{*} : (x \in L) XOR (y \in L)}$ is regular regular if $L$ Recursive.

$♠$ stand for respect under logspace reduction
CVAL= ${⟨ C, x ⟩ : C is boolean circut and C (x) = 1} \in \P -$ complete $♠$
STCON= ${⟨ G, s, t ⟩ : G is a directed graph and exsit path from s to t} \in \P, N L -$ complete $♠$
UHAMPATH= ${⟨ G, s, t ⟩ : G is a undirected graph and exsit ham' path from s to t} \in N P C$
UHAMCYCLE= ${⟨ G ⟩ : G is a undirected graph has Hamiltonian cycle} \in N P C$
SUBSET-SUM= ${⟨ S = s_{1} \dots s_{k}, t ⟩ : \exists T \subseteq S, \sum_{s \in T} s = t} \in N P C$

Theorem

(extended rice) Let $C \subset R E$ s.t $Σ^{*} \notin C, C \neq \emptyset .$ then $L_{C} \notin R E$

L_{C} = {⟨ M ⟩ : M is TM and L (M) \in C} \notin R E

Proof ▼

$\overset{―}{A C C} \leq_{m} L_{C}$ and Let $M_{A}$ be TM that accept some $A \in C$ . Define $f (⟨ M, w ⟩) \mapsto ⟨ B_{M, w} ⟩$ ,
$B_{M, w}$ On input $x$ : Emulate $M_{A} (x)$ and $M (w)$ in parallel, and accept if one of them does.

⟨ M, w ⟩ \in \overset{―}{A C C} \Rightarrow L (B_{M, w}) = A \in C ⟨ M, w ⟩ \notin \overset{―}{A C C} \Rightarrow L (B_{M, w}) = Σ^{*} \notin C

2-NFA with same L

to compare languages accepted by both we have to figure out if L(A) is equal to L(B) or not. Thus, you have to find out if L(A)-L(B) and L(B)-L(A) is null set or not. (Reason1)
Part1: To find this out, we construct NFA X from NFA A and NFA B, . If X is empty set then L(A) = L(B) else L(A) != L(B). (Reason2)
Part2: Now, we have to find out an efficient way of proving or disproving X is empty set. When will be X empty as DFA or NFA? Answer: X will be empty when there is no path leading from starting state to any of the final state of X. We can use BFS or DFS for this. $X = (A \cap B^{'}) \cup (B \cap A^{'}) = \emptyset ?$

(a) L = {⟨ M, w ⟩ M attempts to move its head left when its head is on the leftmost tape cell}

We prove by contradiction that L is undecidable. Assume L was decidable, and let $M *$ be a TM that decides it. We construct a TM, M0 , that decides HP (the halting problem), i.e., we show HP is decidable as well, which is a contradiction. The TM M0 on input hM, wi: i. build a TM, M00 , from M, where M00 shifts w one tape cell to the right, and mark the leftmost tape cell with ]. ii. TM M00 runs M on w. iii. If M00 encounters the ] symbol during the run of M on w, then M00 moves to the right and simulates M reaching the leftmost tape cell. iv. If M halts and accepts, M00 simulates moving its head all the way to the left and off the leftmost tape cell The TM M0 runs $M *$ on the input hM0 , wi. If $M *$ accepts, M0 accepts; otherwise, M0 rejects. Notice that $M *$ always halts (accepts or rejects) since we assumed it is a decider. You can prove now that M00 moves its head off of the leftmost tape cell iff M halts (and accepts) w. It then follows that M0 decides HP, and hence HP is decidable, which is a contradiction. Therfore, the language L is not decidable.

(b) L = {⟨ M, w ⟩ M moves its head left on input w}

The trick to proving this language is decidable is to notice that M moves its head left on an input w if and only if it does so within the first $| w | + | Q | + 1$ steps of its run on w, where $| Q |$ is the number of states of the machine M. Prove it! Therefore, to decide whether an input hM, wi is an instance of L, the decider $M *$ simply runs M on w for at most $| w | + | Q | + 1$ steps and accepts iff M does moves its head left (the correctness of this construction follows immediately after you prove the validity of the above trick)

$A C C B S = {⟨ M, w, k ⟩ M is a TM that accepts w using k cells} \in R$ $b = | Q | \times | Γ |^{k} \times k$ is a bound on the number of k cell configurations of M. Any $f (n)$ space bounded Turing machine also runs in time $2^{O (f (n))}$ . Is this because a configuration consists of a state, a position of the head and the contents of the work tape, which is $| Q | \cdot f (n) \cdot | Γ |^{f (n)}$ If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$ , or it loops forever. That’s because if it runs for at least $k + 1$ time steps, some configuration must be repeated; and if a configuration is repeated, it will continue repeating forever.

Let $| Γ | = 2^{c}$ , i.e., $c = \lg | Γ |$ . Then $| Γ |^{f (n)} = (2^{c})^{f (n)} = 2^{c f (n)} = 2^{O (f (n)}$ . For similar reasons, $| Q | \cdot f (n) \cdot | Γ |^{f (n)} = 2^{O (f (n)}$ . So, the number of possible configurations of a $f (n)$ -space-bounded Turing machine is $2^{O (f (n)}$ , and thus any such machine must either halt in time at most $2^{O (f (n)}$ or loop forever.
${⟨ M ⟩ ∣ M is a Turing machine such that L (M) \in P}$ is undecidable.

{ $⟨ M ⟩ ∣ M is a Turing machine such that M \in P}$ = ${⟨ M ⟩ | (\exists k \forall x) M (x) halts in O (| x |^{k}) time}$ We reduce from the halting problem. Suppose that we are given a machine $M$ , and we are to decide whether $M$ halts on the empty input. We construct a new machine $M^{'}$ accepting a single input $x$ , which operates as follows:

1. Let $n = | x |$ . 2. $M^{'}$ runs $M$ for $n$ steps. 3. If $M$ halted within $n$ steps then $M^{'}$ runs a dummy loop taking exponential time $Ω (2^{n})$ . Otherwise, $M^{'}$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn’t halt then $M^{'}$ runs in polynomial time. If $M$ halts, then $M^{'}$ takes exponential time. Hence $M$ halts iff $M^{'}$ is not polynomial time.

—

More generally, this shows that even if we know that $M$ runs in time at most $f (n)$ for some superpolynomial time-constructible $f$ , then we cannot decide whether $M$ runs in polynomial time.

Proof ▼

ϕ = ⋀_{m = 1}^{n} (x_{m} \lor y_{m} \lor z_{m}) SAT \leq_{p} IndSet

with $m$ clauses, produce the graph $G_{ϕ}$ that contains a triangle for each clause, with vertices of the triangle labeled by the literals of the clause. Add an edge between any two complementary literals from different triangles. Finally, set $k = m$ . In our example, we have triangles on $x, y, \overset{―}{z}$ and on $\overset{―}{x}, w, z$ plus the edges $(x, \overset{―}{x})$ and $(\overset{―}{z}, z)$ .

>We need to prove two directions. First, if $ϕ$ is satisfiable, then $G_{ϕ}$ has an independent set of size at least $k$ . Secondly, if $G_{ϕ}$ has an independent set of size at least $k$ , then $ϕ$ is satisfiable. (Note that the latter is the contrapositive of the implication "if $ϕ$ is not satisfiable, then $G_{ϕ}$ does not have an independent set of size at least k".)

>For the first direction, consider a satisfying assignment for $ϕ$ . Take one true literal from every clause, and put the corresponding graph vertex into a set $S$ . Observe that $S$ is an independent set of size $k$ (where $k$ is the number of clauses in $ϕ$ ).

>For the other direction, take an independent set $S$ of size $k$ in $G_{ϕ}$ . Observe that $S$ contains exactly one vertex from each triangle (clause) , and that $S$ does not contain any conflicting pair of literals (such as $x$ and $\overset{―}{x}$ , since any such pair of conflicting literals are connected by an edge in $G_{ϕ}$ ). Hence, we can assign the value True to all the literals corresponding with the vertices in the set $S$ , and thereby satisfy the formula $ϕ$ .

>This reduction is polynomial in time because $\dots ?$

I’ve looked at many different examples of how this is done, and everything I find online includes everything in the proof except the argument of why this is polynomial. I presume it’s being left out because it’s trivial, but that doesn’t help me when I’m trying to learn how to explain such things.

$L = {⟨ M, 1^{n} ⟩ : M is a TM and exists a string that M accepts in n steps}$ (cook-levin)
a. $L \in N P C$ The witness is a word that M accepts in at most n steps b. $L^{'} \in N P$ and let V be a verifier for $L^{'}$ of running time at most p for some polynomial p. For a string w, let $v_{w}$ be the TM that on input c, emulates $V (w, c)$ . Consider the reduction $f (w) = (⟨ V_{w}, 1^{p (| w |)} ⟩$ It is easy to verify that f is polytime computable, and that $f (w) \in L \leftrightarrow w \in L$

3-SAT: Given a CNF formula

φ

, where every clause in

φ

has *exactly* 3 literals in it, one should determine if there exist an assignment that satisfies it.
Max-2-SAT: Given a CNF formula, where every clause in

ϕ

has *exactly* 2 literals in it, and a positive number

k

, one should determine if there exist an assignment that satisfies *at least*

k

clauses.

Proof ▼

Replace a singleton clause $a$ with $a \lor b$ and many copies of $\neg b \lor c$ , $\neg b \lor \neg c$ . Reductions without extra variables don’t work even when singleton clauses are allowed. There are five types of clauses: $ℓ_{1}, \neg ℓ_{1}, ℓ_{1} \lor ℓ_{2}$ , $ℓ_{1} \lor \neg ℓ_{2}$ , $\neg ℓ_{1} \lor \neg ℓ_{2}$ . Suppose that $k$ of $ℓ_{1}, ℓ_{2}, ℓ_{2}$ are true. The probability that a random clause of each type is true is:

\begin{array}{ccccc} k & 0 & 1 & 2 & 3 \\ ℓ_{1} & 0 & 1 / 3 & 2 / 3 & 1 \\ \neg ℓ_{1} & 1 & 2 / 3 & 1 / 3 & 0 \\ ℓ_{1} \lor ℓ_{2} & 0 & 2 / 3 & 1 & 1 \\ ℓ_{1} \lor \neg ℓ_{2} & 1 & 1 / 3 & 1 / 3 & 1 \\ \neg ℓ_{1} \lor \neg ℓ_{2} & 1 & 1 & 2 / 3 & 0 \end{array}

We would like to take a convex combination of these rows which is of the form

\begin{array}{cccc} α & β & β & β \end{array}

However, all such convex combinations have $α = β$ .

3 S A T \leq_{P} exactly 1/3 SAT

Proof ▼

Let $z$ be a new variable not in $ϕ$ . Let there be $m$ clauses in $ϕ$ . We add $(z \lor \neg z)$ and $2 m + 2$ copies of $(z)$ to $ϕ$ . In every exactly 1/3-satisfying assignment $z$ must be false.

Let $ϕ \land (z \lor \neg z) \land (z) \land (z) \land . . . (2 m + 2)$ copies $. . . \land (z) = ϕ^{'}$ . The following claim is easy to prove.

Claim: $ϕ$ is satisfiable iff $ϕ^{'}$ has exactly 1/3rd satisfiable clauses.

Therfore 3SAT $\leq_{P}$ 1/3-CNFSAT, and hence 1/3-CNFSAT is NP-complete. □

8 Determine if L in P

Resulting regular expres­sion:

8.1 Examples

2-NFA with same L

8 Determine if $L$ in $P$

Resulting regular expression: