Martin

In each case below, find a string of minimum length in $\{a,b\}^*$ not in the language corresponding to the given regular expression.

Consider the two regular expressions

Let $r$ and $s$ be arbitrary regular expressions over the alphabet $\Sigma$. In each case below, find a simpler equivalent regular expression.

It is not difficult to show using mathematical induction that for every integer $n\ge2$, there are nonnegative integers $i$ and $j$ such that $n=2i+3j$. With this in mind, simplify the regular expression $(aa+aaa)(aa+aaa)^*$.

In each case below, give a simple description of the smallest set of languages that contains all the “basic” languages $\varnothing$, $\{\Lambda\}$, and $\{\sigma\}$ (for every $\sigma\in\Sigma$) and is closed under the specified operations.

Suppose $w$ and $z$ are strings in $\{a,b\}^*$. Find regular expressions corresponding to each of the languages defined recursively below.

Find a regular expression corresponding to each of the following subsets of $\{a,b\}^*$.

Show that every finite language is regular.

The star height of a regular expression $r$ over $\Sigma$, denoted by $sh(r)$, is defined as follows:

Find the star heights of the following regular expressions.

For both the regular expressions in the previous exercise, find an equivalent regular expression of star height 1.

Let $c$ and $d$ be regular expressions over $\Sigma$.

Describe precisely an algorithm that could be used to eliminate the symbol $\varnothing$ from any regular expression that does not correspond to the empty language.

Describe an algorithm that could be used to eliminate the symbol $\Lambda$ from any regular expression whose corresponding language does not contain the null string.

The order of a regular language $L$ is the smallest integer $k$ for which $L^k=L^{k+1}$, if there is one, and $\infty$ otherwise.

† A generalized regular expression is defined the same way as an ordinary regular expression, except that two additional operations, intersection and complement, are allowed. So, for example, the generalized regular expression $abb\varnothing'\cap(\varnothing'aaa\varnothing')'$ represents the set of all strings in $\{a,b\}^*$ that start with $abb$ and don’t contain the substring $aaa$.

Figure 3.34 shows a transition diagram for an NFA. For each string below, say whether the NFA accepts it.

Find a regular expression corresponding to the language accepted by the NFA pictured in Figure 3.34. You should be able to do it without applying Kleene’s theorem: First find a regular expression describing the most general way of reaching state 4 the first time, and then find a regular expression describing the most general way, starting in state 4, of moving to state 4 the next time.

For each of the NFAs shown in Figure 3.35, find a regular expression corresponding to the language it accepts.

The following is the transition table for an NFA with states 1–5 and input alphabet $\{a,b\}$. There are no $\Lambda$-transitions.

A transition table is given for an NFA with seven states.

Find:

A transition table is given for another NFA with seven states.

Calculate $\delta^*(1,ba)$.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA with no $\Lambda$-transitions. Show that for every $q\in Q$ and every $\sigma\in\Sigma$, $\delta^*(q,\sigma)=\delta(q,\sigma)$.

It is easy to see that if $M=(Q,\Sigma,q_0,A,\delta)$ is an FA accepting $L$, then the FA $M'=(Q,\Sigma,q_0,Q-A,\delta)$ accepts $L'$ (the FA obtained from Theorem 2.15 by writing $L'=\Sigma^*-L$ is essentially $M'$). Does this still work if $M$ is an NFA? If so, prove it. If not, find a counterexample.

In Definition 3.14, $\delta^*$ is defined recursively in an NFA by first defining $\delta^*(q,\Lambda)$ and then defining $\delta^*(q,y\sigma)$, where $y\in\Sigma^*$ and $\sigma\in\Sigma$. Give an acceptable recursive definition in which the recursive part of the definition defines $\delta^*(q,\sigma y)$ instead.

Which of the following, if any, would be a correct substitute for the second part of Definition 3.14? Give reasons for your answer.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA. This exercise involves properties of the $\Lambda$-closure of a set $S$. Since $\Lambda(S)$ is defined recursively, structural induction can be used to show that $\Lambda(S)$ is a subset of some other set.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA. A set $S\subseteq Q$ is called $\Lambda$-closed if $\Lambda(S)=S$.

† Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA. Show that for every $q\in Q$ and every $x,y\in\Sigma^*$,

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an FA, and let $M_1=(Q,\Sigma,q_0,A,\delta_1)$ be the NFA with no $\Lambda$-transitions for which $\delta_1(q,\sigma)=\{\delta(q,\sigma)\}$ for every $q\in Q$ and $\sigma\in\Sigma$. Show that for every $q\in Q$ and $x\in\Sigma^*$, $\delta_1^*(q,x)=\{\delta(q,x)\}$. Recall that the two functions $\delta^*$ and $\delta_1^*$ are defined differently.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA accepting a language $L$. Assume that there are no transitions to $q_0$, that $A$ has only one element, $q_f$, and that there are no transitions from $q_f$.

Give an example of a regular language $L$ containing $\Lambda$ that cannot be accepted by any NFA having only one accepting state and no $\Lambda$-transitions, and show that your answer is correct.

Can every regular language not containing $\Lambda$ be accepted by an NFA having only one accepting state and no $\Lambda$-transitions? Prove your answer.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA, let $m$ be the maximum size of any of the sets $\delta^*(q,\sigma)$ for $q\in Q$ and $\sigma\in\Sigma$, and let $x$ be a string of length $n$ over the input alphabet.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA. The NFA $M_1$ obtained by eliminating $\Lambda$-transitions from $M$ might have more accepting states than $M$, because the initial state $q_0$ is made an accepting state if $\Lambda(\{q_0\})\cap A\ne\varnothing$. Explain why it is not necessary to make all the states $q$ for which $\Lambda(\{q\})\cap A\ne\varnothing$ accepting states in $M_1$.

In each part of Figure 3.36 is pictured an NFA. Use the algorithm described in the proof of Theorem 3.17 to draw an NFA with no $\Lambda$-transitions accepting the same language.

Each part of Figure 3.37 pictures an NFA. Using the subset construction, draw an FA accepting the same language. Label the final picture so as to make it clear how it was obtained from the subset construction.

Suppose $L\subseteq\Sigma^*$ is a regular language. If every FA accepting $L$ has at least $n$ states, then every NFA accepting $L$ has at least $\underline{\qquad}$ states. (Fill in the blank, and explain your answer.)

Each part of Figure 3.38 shows an NFA. Draw an FA accepting the same language.

For each of the following regular expressions, draw an NFA accepting the corresponding language, so that there is a recognizable correspondence between the regular expression and the transition diagram.

For part (e) of Exercise 3.41, draw the NFA that is obtained by a literal application of Kleene’s theorem, without any simplifications.

Suppose $M=(Q,\Sigma,q_0,A,\delta)$ is an NFA accepting a language $L$. Let $M_1$ be the NFA obtained from $M$ by adding $\Lambda$-transitions from each element of $A$ to $q_0$. Describe (in terms of $L$) the language $L(M_1)$.

Suppose $M=(Q,\Sigma,q_0,A,\delta)$ is an NFA accepting a language $L$.

Suppose $M$ is an NFA with exactly one accepting state $q_f$ that accepts the language $L\subseteq\{a,b\}^*$. In order to find NFAs accepting the languages $\{a\}^*L$ and $L\{a\}^*$, we might try adding $a$-transitions from $q_0$ to itself and from $q_f$ to itself, respectively. Draw transition diagrams to show that neither technique always works.

In the construction of $M_u$ in the proof of Theorem 3.25, consider this alternative to the construction described: Instead of a new state $q_u$ and $\Lambda$-transitions from it to $q_1$ and $q_2$, make $q_1$ the initial state of the new NFA, and create a $\Lambda$-transition from it to $q_2$. Either prove that this works in general, or give an example in which it fails.

In the construction of $M_c$ in the proof of Theorem 3.25, consider the simplified case in which $M_1$ has only one accepting state. Suppose that we eliminate the $\Lambda$-transition from the accepting state of $M_1$ to $q_2$, and merge these two states into one. Either show that this would always work in this case, or give an example in which it fails.

In the construction of $M^*$ in the proof of Theorem 3.25, suppose that instead of adding a new state $q_0$, with $\Lambda$-transitions from it to $q_1$ and to it from each accepting state of $Q_1$, we make $q_1$ both the initial state and the accepting state, and create $\Lambda$-transitions from each accepting state of $M_1$ to $q_0$. Either show that this works in general, or give an example in which it fails.

Figure 3.39 shows FAs $M_1$ and $M_2$ accepting languages $L_1$ and $L_2$, respectively. Draw NFAs accepting each of the following languages, using the constructions in the proof of Theorem 3.25.

Draw NFAs with no $\Lambda$-transitions accepting $L_1L_2$ and $L_2L_1$, where $L_1$ and $L_2$ are as in Exercise 3.49. Do this by connecting the two given diagrams directly, by arrows with appropriate labels.

Use the algorithm of Theorem 3.30 to find a regular expression corresponding to each of the FAs shown in Figure 3.40. In each case, if the FA has $n$ states, construct tables showing $L(p,q,j)$ for each $j$ with $0\le j\le n-1$.

Suppose $M$ is an FA with the three states 1, 2, and 3, and 1 is both the initial state and the only accepting state. The expressions $r(p,q,2)$ corresponding to the languages $L(p,q,2)$ are shown in the table below. Write a regular expression describing $L(M)$.

Suppose $\Sigma_1$ and $\Sigma_2$ are alphabets, and the function $f:\Sigma_1^*\to\Sigma_2^*$ is a homomorphism; i.e., $f(xy)=f(x)f(y)$ for every $x,y\in\Sigma_1^*$.

Suppose $M=(Q,\Sigma,q_0,A,\delta)$ is an NFA. For two (not necessarily distinct) states $p$ and $q$, we define the regular expression $e(p,q)$ as follows: $e(p,q)=l+r_1+r_2+\cdots+r_k$, where $l$ is either $\Lambda$ (if $\delta(p,\Lambda)$ contains $q$) or $\varnothing$, and the $r_i$’s are all the elements $\sigma$ of $\Sigma$ for which $\delta(p,\sigma)$ contains $q$. It’s possible for $e(p,q)$ to be $\varnothing$, if there are no transitions from $p$ to $q$; otherwise, $e(p,q)$ represents the “most general” transition from $p$ to $q$.

If we generalize this by allowing $e(p,q)$ to be an arbitrary regular expression over $\Sigma$, we get what is called an expression graph. If $p$ and $q$ are two states in an expression graph $G$, and $x\in\Sigma^*$, we say that $x$ allows $G$ to move from $p$ to $q$ if there are states $p_0,p_1,\ldots,p_m$, with $p_0=p$ and $p_m=q$, such that $x$ corresponds to the regular expression $e(p_0,p_1)e(p_1,p_2)\cdots e(p_{n-1},p_n)$. This allows us to say how $G$ accepts a string $x$ ($x$ allows $G$ to move from the initial state to an accepting state), and therefore to talk about the language accepted by $G$. It is easy to see that in the special case where $G$ is simply an NFA, the two definitions for the language accepted by $G$ coincide. It is also not hard to convince yourself, using Theorem 3.25, that for any expression graph $G$, the language accepted by $G$ can be accepted by an NFA.

We can use the idea of an expression graph to obtain an alternate proof of Theorem 3.30, as follows. Starting with an FA $M$ accepting $L$, we may easily convert it to an NFA $M_1$ accepting $L$, so that $M_1$ has no transitions to its initial state $q_0$, exactly one accepting state $q_f$ (which is different from $q_0$), and no transitions from $q_f$. The remainder of the proof is to specify a reduction technique to reduce by one the number of states other than $q_0$ and $q_f$, obtaining an equivalent expression graph at each step, until $q_0$ and $q_f$ are the only states remaining. The regular expression $e(q_0,q_f)$ then describes the language accepted. If $p$ is the state to be eliminated, the reduction step involves redefining $e(q,r)$ for every pair of states $q$ and $r$ other than $p$.

Describe in more detail how this reduction can be done. Then apply this technique to the FAs in Figure 3.40 to obtain regular expressions corresponding to their languages.