7
0
An LTL Formula l is defined by the following grammar (where <x> describes the non-terminal symbol x):
<l> ::= <b> | F <l> | G <l> | X <l> | (<l> U <l>) | (<l> W <l>) | (<l> R <l>)
| (<l> & <l>) | (<l> \| <l>) | !<l>
<b> ::= BVar | True | False | (<i> < <i>) | (<i> <= <i>) | (<i> > <i>) | (<i> >= <i>)
| (<i> = <i>) | (<i> != <i>)
<i> ::= IVar | -128 | -127 | ... | 127 | (<i> + <i>) | (<i> - <i>)
| (<i> * <i>) | (<i> / <i>)
(I escaped a pipe to denote boolean or. You should not print that backslash in your output)
BVar and IVar represent variables of boolean and integral types respectively. Each must be one of four possible single character variable names, and there may by no overlap between BVar and IVar. For instance, you may choose a,b,c,d for BVar and w,x,y,z for IVar
Note that all binary operators must have parentheses around them and that no other parentheses are allowed.
Your task is to write a function that takes one input encoding the maximal nesting depth of an LTL formula and prints a random formula limited by that depth (but not necessarily exactly that depth). The distribution does not have to be uniformly random, but each possible formula has to have a non-zero chance of being generated.
You may use ≤, ≥, and ≠ instead of <=, >=, and !=.
You may add or remove whitespace as you see fit. Even no whitespace at all is allowed.
Examples:
f(0) -> True
f(0) -> d
f(1) -> (a&b)
f(1) -> Fd
f(1) -> (x<y)
f(3) -> (G(x!=y)|Fb)
f(3) -> (x<(w+(y+z)))
Standard loopholes are forbidden.
This is code-golf, so the shortest code in bytes wins.
May we use
≤
,≥
, and≠
instead of<=
,>=
, and!=
? – Adám – 2017-10-20T10:33:38.547That is allowed. I will update the challenge accordingly. – Sacchan – 2017-10-20T10:35:15.347
3What is the "nesting depth"? – Peter Taylor – 2017-10-20T12:50:26.777
1Is everything in
<i>
evenly divided in terms of randomness? So these four(<i> + <i>) | (<i> - <i>) | (<i> * <i>) | (<i> / <i>)
each have a chance of 1/260 to occur (and -128 through 127 also each has a 1/260 chance to occur)? – Kevin Cruijssen – 2017-10-20T13:35:32.187@PeterTaylor I think (not sure) this refers to the maximum depth of
<i>
. – Kevin Cruijssen – 2017-10-20T13:42:13.383Hmm, I guess this also means that if the input is 0, the integer -128 through 127 have a 1/256 change of occurring for
<i>
; if the input is 1 it at first has first a 1/260 chance of occurring, and if it happens to be+-*/
(4/260 chance), the next time it randomly selects<i>
it has a 1/256 chance again because we have reached our maximum nested depth. Am I understanding what you've meant with maximal nested depth correctly, @Sacchan? – Kevin Cruijssen – 2017-10-20T13:43:59.203@KevinCruijssen The probabilities do not have to be equal. As I stated, every part just has to have a non-zero probability of occurring.
Nesting depth refers to the longest path in the syntax tree of the formula. If you have a depth of zero, you can only have a node without children (such as a constant or a variable). A nesting depth of 1 gives a unary or binary operator with the children having a nesting depth of at most 0. And so forth. – Sacchan – 2017-10-20T14:13:23.177
<l>
cannot derive55
, as far as I can see. And the path in the syntax tree forTrue
has length 2:<l> -> <b> -> True
– rici – 2017-10-20T17:34:11.660It seems (from the examples) that we should read "maximal nesting depth of an LTL formula" liteally (i.e. it is the nesting depth of the resulting formula rather than that of the syntax tree path taken, as assumed by @rici above). Could you clarify this? – Jonathan Allan – 2017-10-21T15:12:50.007
Also, if I am correct, could you clarify whether the nesting depth of
Fd
would be zero or one? – Jonathan Allan – 2017-10-21T15:25:44.437@rici: You are correct, 55 was an erroneous example. I have removed it. – Sacchan – 2017-10-22T10:29:20.427
@Jonathan Allan: You are correct. Fd would be a nesting depth of one (since the Tree would have F as root node and d as its child) – Sacchan – 2017-10-22T10:29:23.440