How can I define this syntax? [closed]

Question

I wanted to define syntax for a graph path considering it may branch out anywhere.

For instance, I have a path going from a to e following b, c, d: a, b, c, d, e.

Let's consider it (may) branches from b now: a, b, (x | y), d, e which actually means three different paths:

1) a, b, d, e

2) a, b, x, d, e

3) a, b, y, d, e

So, each parenthesis actually means "the path might either go through any of the nodes defined in the parenthesis connecting the node just before parenthesis and right after parenthesis or through none of the nodes defined in the parenthesis".

With more inner parenthesis, a single string line may generate even more paths. For instance: a, b, (x | (z | t) | y), d, e which means these five paths:

1) a, b, d, e

2) a, b, x, d, e

3) a, b, y, d, e

4) a, b, z, d, e

5) a, b, t, d, e

6) a, b, z, y, d, e

7) a, b, t, y, d, e

8) a, b, x, z, d, e

9) a, b, x, t, d, e

So, how can I define this syntax mathematically?

Answer 1

You are mixing two things here: syntax and semantics.

First, syntax. What is the language of strings $L_P \subseteq \Sigma^*$ with $\Sigma = \{\mathtt{a}, \dots, \mathtt{z}, \mathtt{)}, \mathtt{(}, \mathtt{,}\}$ that describe a set of paths as you specify them? You can specify $L_P$ by the formal grammar

$\qquad\begin{align} S &\to T\mathtt{,} S \mid \mathtt{(}S\mathtt{)}S \mid T \\ T &\to [\mathtt{a}\dots\mathtt{z}] \end{align}$

Note that the key feature is recursion for the parts inside parentheses. Depending on the parsing algorithm you want to employ, you may have to refactor this grammar.

Next, which set of paths does a given string $p \in L_p$ describe? Note that this is independent of the syntax; we could define anything we want as the meaning of $p$. Your specification is quite precise, and can be described by these by recursive functions:

$\qquad\begin{align} \varphi(t) &= \{t\} \quad, t \in [\mathtt{a}\dots\mathtt{z}], \\ \varphi(t\mathtt{,}w) &= \varphi(t) \cdot \varphi(w) \quad, t \in [\mathtt{a}\dots\mathtt{z}], w \in \Sigma^*, \\ \varphi((v)w) &= (\psi(v), \{\varepsilon\}) \cdot \varphi(w) \quad, v, w \in \Sigma^* \\ \end{align}$

and

$\qquad\begin{align} &\psi(t) = \{t\} \quad, \mathtt{t} \in [\mathtt{a}\dots\mathtt{z}], \\ &\psi(t\mathtt{,}w) = \psi(t) \cup \psi(w) \quad, t \in [\mathtt{a}\dots\mathtt{z}], w \in [\mathtt{a}\dots\mathtt{z},\mathtt{,}]^*, \\ &\psi(v_0(w_1)v_1(w_2) \dots v_{k-1}(w_k)v_k) = \\ &\phantom{=}\bigcup_{i \in [0..k]} (\psi(w_1), \{\varepsilon\}) \cdot \dots \cdot (\psi(w_{i}), \{\varepsilon\}) \cdot \psi(v_i) \cdot (\psi(w_{i+1}), \{\varepsilon\}) \cdot \dots \cdot (\psi(w_k), \{\varepsilon\}) \quad, v_i \in [\mathtt{a}\dots\mathtt{z},\mathtt{,}]^*, w_i \in L_P. \\ \end{align}$

Note how $\varphi(p) \subseteq [\mathtt{a}\dots\mathtt{z}]^*$ is the set of paths described by $p$.

Warning: Your syntax has the troublesome feature that a comma-separated list of path elements has different meaning outside and inside of parenteses (resulting in two functions for the semantics). In combination with your semantics, that means e.g. that you can not describe the set of paths $\{ad, abcd\}$.

Warning: Your semantics have the troublesome feature that any list of atoms in parentheses may produce at most one atom (selection), but if one element of the list is another list we suddenly get more (selection + concatenation). In other words, the semantic of $\mathtt{,}$ inside of parentheses changes depending on context. This is what makes the semantics so horrible. But then, maybe that is how it has to be: you seem to want it that way.