3

Question:

Define NFA for the following languages :

  1. $L_1=\{\sigma w \sigma\big| \sigma\in\{a,b,c\},w\in\{a,b,c\}^*\}$
  2. $L_n=\{w\in\{0,1\}^* \big| the \ n^{th} \ from \ last \ char\ is\ 1\}$

$Solution.A.$ we define NFA for $L_1$. Let $$A=( Q,\Sigma ,q_{0} ,\delta ,F)$$such that,$$ \begin{array}{l} Q=\{q_{0} ,q_{1} ,q_{2}\}\\ \Sigma =\{a,b,c\}\\ F=\{q_{2}\} \end{array}$$ and let $\displaystyle \delta :( Q\times \Sigma )\rightarrow \mathcal{P}( Q)$ the transition function such that: $$\forall \sigma \in \Sigma :\delta (\{q_{0}\} ,\sigma ) =\{q_{1}\} \land \delta (\{q_{2}\} ,\sigma ) =\{q_{1} ,q_{2}\} \land \delta ( q_{2} ,\Sigma \backslash \{\sigma \}) =\{q_{1}\}$$ $Solution.B. $ we define NFA for $L_n$. Let $$A=( Q,\Sigma ,q_{0} ,\delta ,F)$$such that, $$ \begin{array}{l} Q=\{q_{0} ,q_{1} ,q_{2} ,\dotsc ,q_{n}\}\\ \Sigma =\{0,1\}\\ F=\{q_{n}\} \end{array}$$and let $\delta :( Q\times \Sigma )\rightarrow \mathcal{P}( Q)$ the transition function such that:$$ \begin{array}{l} \delta (\{q_{0}\} ,0) =\{q_{0}\} \ \\ \delta (\{q_{0}\} ,1) =\{q_{0} ,q_{1}\}\\ \forall n\geq 2,i\in [ 2,n] :\delta (\{q_{i-1}\} ,\sigma ) =\{q_{i}\} \end{array}$$

I am not sure whether I wrote the definition properly in terms of formally. Therefore, I will be glad to see what you think about it. Thanks!

Chopin
  • 872
  • Your Solution $A$ is conceptually wrong (it doesn't do what is supposed to do) and formally meaningless (the definition of $\delta(q_2,\Sigma\setminus{\sigma})$ is abstract nonsense: what does $\Sigma\setminus{\sigma}$ mean?). Note that $L_1$ is the language of the words over${a,b,c}$ with at least two characters such that its first and the last characters are the same. Do you see how to fix your NFA? – Taroccoesbrocco Nov 06 '21 at 09:10
  • @Taroccoesbrocco why is it wrong? I will be grateful if you can tell me what is wrong, and why what I wrote is nonsense because I really don't know how to define it properly. If it is conceptually wrong then what is the concept? In addition, what do you think about solution B? – Chopin Nov 06 '21 at 09:14
  • @Taroccoesbrocco oh I see what you are telling me now, I thought about it. Solution A is wrong because I wrote in the function a group of 2 chars, and $\delta$ only accepts one. Right? – Chopin Nov 06 '21 at 09:18
  • It's hard to give you a more precise answer, because I don't understand the definition of $\delta(q_2,\Sigma\setminus{\sigma})$. What does $\Sigma\setminus{\sigma}$ mean? What is the transition function $\delta$ supposed to do on the state $q_2$? More generally, what is the informal and intuitive definition of your NFA for Solution $A$? If we first make your intuition clear, then we can formalize it properly. I suspect there are two kinds of error in your Solution $A$: at the informal level (what is your NFA is supposed to do) and at the formal level (how to formalize your intuition). – Taroccoesbrocco Nov 06 '21 at 09:24
  • When you define the transition function $\delta$, you have to say how $\delta$ behaves with every state and every character. So, if your set of states is ${q_0, q_1, q_2}$ and your alphabet is ${a,b,c}$, you have to define $\delta(q_0, a) = \dots$, $\delta(q_0, b) = \dots$, $\delta(q_0, c) = \dots$, $\delta(q_1, a) = \dots$, $\delta(q_1, b) = \dots$, and so on. If $\delta(q_0, a) = \delta(q_0, b) = \delta(q_0, c)$, it makes sense to simply define $\delta(q_0, \sigma) = \dots$ (for any $\sigma \in \Sigma$), but writing $\delta(q_0, \Sigma\setminus\sigma) = \dots$ is abstract nonsense. – Taroccoesbrocco Nov 06 '21 at 09:39
  • @Taroccoesbrocco right. Can I give it a fix and then can you see it and tell me whether it's good or not? – Chopin Nov 06 '21 at 09:40
  • Sure! No problem. Hint: in Solution $A$ you need more than three states. – Taroccoesbrocco Nov 06 '21 at 09:48
  • @Taroccoesbrocco I thought fixing it like this: $$\forall \sigma \in \Sigma \left[ \delta ({q_{0}} ,\sigma ) ={q_{1}} \land \delta ({q_{2}} ,\sigma ) ={q_{1} ,q_{2}} \land \forall \sigma ^{} \in \Sigma \backslash {\sigma } :\delta \left( q_{2} ,\sigma ^{}\right) ={q_{1}}\right]$$ – Chopin Nov 06 '21 at 09:59
  • @Taroccoesbrocco or more accurate is to just simply make 3 states for each $\sigma \in \Sigma$? – Chopin Nov 06 '21 at 10:22
  • What does $\sigma^* \in \Sigma \setminus {\sigma}$ mean? What do you want to say, informally? If you can provide a more explicit definition of the transition function $\delta$, in the style I sketched in a previous comment, I can at least understand your definition. Moreover, your definition of $\delta$ is incomplete, it doesn't say anything about the behavior of $\delta$ when its state argument is $q_1$. – Taroccoesbrocco Nov 06 '21 at 10:37
  • 1
    @Taroccoesbrocco what do you say about it? $$ \begin{array}{l} Q={q_{0} ,q_{1} ,q_{2} ,q_{3} ,q_{4}}\ \Sigma ={a,b,c}\ F={q_{4}}\ \ \ \delta ({q_{0}} ,a) =\delta ({q_{1}} ,b) =\delta ({q_{1}} ,c) ={q_{1}}\ \delta ({q_{0}} ,b) =\delta ({q_{2}} ,a) =\delta ({q_{2}} ,c) ={q_{2}}\ \delta ({q_{0}} ,c) =\delta ({q_{3}} ,a) =\delta ({q_{3}} ,b) ={q_{3}}\ \delta ({q_{1}} ,a) ={q_{1} ,q_{4}}\ \delta ({q_{2}} ,b) ={q_{2} ,q_{4}}\ \delta ({q_{3}} ,c) ={q_{3} ,q_{4}} \end{array}$$ – Chopin Nov 06 '21 at 10:40
  • Great! Perfect, except for a formal mistake. The function $\delta$ is from $Q \times \Sigma$ to $\mathcal{P}(Q)$, so its first argument must be and element of $Q$ ($q_0$, or $q_1$, and so on) and not the singleton of an element of $Q$ (${q_0}$, or ${q_1}$, and so on). For instance, $\delta({q_1}, a) = {q_1, q_4}$ must be $\delta(q_1, a) = {q_1, q_4}$, and $\delta({q_0},a) = δ({q_1},b)=δ({q_1},c) = {q_1}$ must be $\delta(q_0,a)=δ(q_1,b)=δ(q_1,c) = {q_1}$. – Taroccoesbrocco Nov 06 '21 at 11:15
  • @Taroccoesbrocco oh you're right. Btw, what do you say about solution B? considering that I fixed the {} in delta – Chopin Nov 06 '21 at 11:18
  • Your Solution $B$ is great! +1! Provided that you remove "${$" and "$}$" from the first argument in the definition of the transition function $\delta$, and that $\sigma$ stands for any character in the alphabet $\Sigma$ in the last case of the definition of $\delta$. – Taroccoesbrocco Nov 07 '21 at 14:22

0 Answers0