1

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?

davidliu224
  • 33
  • Note that $A = {w \mid w \in {0, 1}^*, |w| \geq 4}$ . Can you solve the exercise for this language? – Kapur Apr 10 '20 at 17:02
  • 1
    @Kapur: No, $0011\notin A$, for instance. The substrings consisting of the first two and the last two characters must be equal. – Brian M. Scott Apr 10 '20 at 17:04
  • @BrianM.Scott Oh, sorry, my bad. – Kapur Apr 10 '20 at 17:04
  • Welcome to MSE. You'll get a lot more help, and fewer votes to close, if you show that you have made a real effort to solve the problem yourself. What are your thoughts? What have you tried? How far did you get? Where are you stuck? This question is likely to be closed if you don't add more context. Please respond by editing the question body. Many people browsing questions will vote to close without reading the comments. – saulspatz Apr 10 '20 at 17:05
  • That notation means that the words of $A$ are those that can be decomposed into three substrings with the following properties. The first substring, $v$, is two characters long. The last substring is identical to the first substring. And the middle substring can be any string of zeroes and ones (including the empty string). – Brian M. Scott Apr 10 '20 at 17:13
  • In order to give its formal description, you must specify the state set, the input alphabet, the transition function, the initial state, and the set of final (acceptor) states, as described here, for instance. – Brian M. Scott Apr 10 '20 at 21:18

1 Answers1

1

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/.

Abraham
  • 252