Constructing an NFA

65 Views Asked by At

For a string $x$, we use the notation $|x|$ to denote the length of (number of characters in) string $x$. Give an NFA (both the state diagram and the formal description) that recognizes the following language $A$ over alphabet $\Sigma = \{0, 1\}$:

$$A = \{vwv\mid v,w \in \{0,1\}^∗,|v| = 2\}$$

I guess what I'm confused about its the usage of v and w. Usually the problems I see just use w, or one variable.

Also, what is meant by its formal description?

1

There are 1 best solutions below

0
On

I believe you have already gotten the help you needed from the comments, but I wanted to answer this question for completeness and for other people reading this post.

Like user @Brian M. Scott said in the comments, $vwv$ means that the string has three parts, with the first and last ($v$) being the same. Also, he linked a wikipedia article that describes the formal definition.


$|v|=2$ means that the length of $v$ is exactly 2. Since your alphabet is $\Sigma = \{0,1\}$, the $4$ possibilities for $v$ are $00,01,10,11$.

This means that your string, $vwv$, could be $00w00, 01w01, 10w10, 11w11$, where $w$ is $\{0,1\}^*$.

The NFA for this would look like:NFA solution

The formal description would be something like $M = (\{q0,q1,...,q14\},\{0,1\},\delta,q0,\{q11,q12,q13,q14\})$ where $\delta$ is described as in the graph above.

I drew this NFA using http://madebyevan.com/fsm/.