# Optimal Opacity-Enforcing Supervisory Control of Discrete Event Systems on Choosing Cost
## 5 Scenario 1: Secret \(K\) Is Opaque with Respect to \(L(G)\) and \(\Sigma_{a}\)
### Case 1: \(\overline{K}=L(G)\)
```
1:for\([s]\in R\)do
2:for\(s\in[s]\)do
3: let \(n\) be the length of \(s\), and \(s\) is denoted by \(s=\sigma_{1}\sigma_{2}\cdots\sigma_{n}\)
4:\(i=n-1\)
5: take \(s=s_{i}t\), and suppose that \(s_{i}=\sigma_{1}\cdots\sigma_{i}\), \(t=\sigma_{i+1}\cdots,\sigma_{n}\)
6:while\(i<n\)do
7:if\(i==-1\)then
8:\(s_{i}=\epsilon\)
9: Break
10:endif
11:if\(s_{i}\in\overline{\mathbb{K}}\)then
12: Break
13:endif
14:\(i=i-1\)
15:endwhile
16: compute the cost \(t\) after \(s_{i}\), that is \(V_{s_{i}}(t)\)
17:endfor
18:endfor
19:return\(V=\{V_{s_{i}}(t)|s^{\prime}=s_{i}t,s^{\prime}\in[s],s_{i}\in\overline{ \mathbb{K}},s_{i}\sigma_{i+1}\in\overline{\mathbb{K}}-\overline{\mathbb{K}}\}\)
```  
**Algorithm 5** Finding the set of strings \(\text{Label}_{t_{i}}=function2(H,V)\) whose choosing cost of the path from the starting node is minimal  
**Input:**\(H=\{H_{1},H_{2},\cdots,H_{|H|}\}\) and \(V\), where \(|H|\) is the number of the elements of \(H\);  
**Output:** the strings set \(\text{Label}_{t_{i}}\) of the shorted path from the starting node to the ending node. ```
1:\(H_{0}=\{t_{s}\}\)
2:\(\text{Label}_{t_{i}}=\{t_{s}\}\)
3:for\(j=1:1:|H|\)do
4:for\(s\in H_{j}\)do
5:if\(j=1\)then
6:\(a_{t_{s},s}=V_{s_{i}}(t)\)
7:\(\text{Labels}_{t_{i}}\cup\{s\}\)
8:\(V_{\min}(s)=a_{t_{s},s}\)
9:else
10:for\(s^{\prime}\in H_{j-1}\)do
11:\(a_{s^{\prime},s}=function3(s^{\prime},s,\text{Label}_{s^{\prime},V_{\min}(s^{ \prime})})\)
12:\(V_{s^{\prime}}(s)=V_{\min}(s^{\prime})+a_{s^{\prime},s}\)
13:endfor
14:\(s^{\prime}=\arg\min\{V_{\min}(s),s^{\prime}\in H_{j-1}\}\)
15:\(\text{Labels}_{t}=\text{Label}_{s^{\prime}}\cup\{s\}\)
16:\(V_{\min}(s)=V_{s^{\prime}}(s)\)
17:endif
18:endfor
19:endfor
20:\(H_{j+1}=\{t_{i}\}\)
21:for\(s\in H_{j}\)do
22:\(a_{s_{j},t_{i}}=0\)
23:endfor
24:\(s^{\prime}=\arg\min\{V_{\min}(s)|s\in H_{|H|}\}\)
25:\(\text{Label}_{t_{i}}=\text{Label}_{s^{\prime}}\cup\{t_{i}\}\)
26:return\(\text{Label}_{t_{i}}\)
```  
**Algorithm 6** Finding the set of strings \(\text{Label}_{t_{i}}=function2(H,V)\) whose choosing cost of the path from the starting node is minimal According to the calculation process of Algorithm 3, we have the following theorem to show the solution of Model (2):  
**Theorem 4**. : _We consider system \(G\) and secret \(K\subseteq L(G)\). In Case 3 of Scenario 1, closed-loop behavior \(L(f/G)\) produced in Algorithm 3 is an optimal solution of Model (2)._  
Proof. : We first show that closed-loop behavior \(L(f/G)\) produced in Algorithm 3 is a feasible solution of optimal Model (2). 1. Proof of the opacity (the first constraint condition). As shown in Case 3, the secret of \(K-\underline{K}\) can be confused by the non-secret strings of \(\overline{K}\). For \(\underline{K}\), all the non-secrets in \(L(G)\) which cannot be distinguished form the secret in \(\underline{K}\) are in \(\cup_{j}H_{j}\) of Line 12. At Lines 14 and 15, string \(s_{i}\) is from \(H_{i}\), where \(i=\{1,2,\cdots,j-1\}\). At Lines 15 and 16, we have \(\overline{K}\subseteq L(f/G)\) and \(\{s_{1},s_{2},\cdots,s_{j-1}\}\subseteq L(f/G)\). So, closed-loop behavior \(L(f/G)\) produced in Algorithm 3 can ensure the opacity of secret \(K\). 2. Proof of the secret remaining in the closed-loop system being maximal (the second constraint condition). According to Lines 15 and 16, it holds that \(\overline{K}\subseteq L(f/G)\). So, the second constraint condition is true. To sum up, the closed-loop behavior \(L(f/G)\) obtained in Algorithm 3 is a feasible solution of optimal Model (2). Secondly, we show that the discount total choosing cost of closed-loop behavior \(L(f/G)\) produced by Algorithm 3 is minimal. Since it holds that \(\overline{K}\subseteq L(f/G)\), the discount total choosing cost of \(L(f/G)\) can be computed as follows: \[V(L(f/G))=V(\overline{K})+V(L(f/G)-\overline{K}).\] (3)  
\(V(\overline{K})\) is finite. To minimize the discount total choosing cost of \(L(f/G)\), we need to show \(V(L(f/G)-\overline{K})\) is minimal using Formula (3).