Is there a way to figure out what the following CFG accepts?

$\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid\; \thicksim p \end{align}$

I'm confused by the boolean algebra symbols. I know the first is S or T, the second is T and F and the third is not p but I'm not sure how they affect the grammar itself.

  • 3
    $\begingroup$ $\lor,\land $ and $\sim$ are probably terminal symbols here. Other than that, any grammar $G$ accepts the language $L(G)$ which is a well-defined notion. Which representation are you looking for? $\endgroup$ – Raphael Feb 12 '14 at 8:58
  • $\begingroup$ @babou: I deleted my remarks, they add little value even after correction. $\endgroup$ – reinierpost Feb 17 '14 at 16:59

A grammar generates a language, it doesn't accept it. Automata accept languages.

The whole point of gramars is that they are easily able to generate quite complex languages. Even regular languages (accepted by finite automata or denoted by regular expressions) can be very hard to describe in simple terms.

In this case, the grammar generates (a subset of) logical formulas, with connectives and ($\wedge$), or ($\vee$), and not ($\thicksim$).

  • $\begingroup$ Would you mind describing the language generated by the CFG a little more, with maybe a couple of sample strings? $\endgroup$ – UndefinedReference Feb 11 '14 at 21:57
  • 2
    $\begingroup$ @navlag: That's your job; apply how the grammar works (i.e. the definition of what/how it derives stuff). $\endgroup$ – Raphael Feb 12 '14 at 9:00

This accepts all the expressions involving 1 variable, sum of products (minterms) expressions.

This grammar makes the priority of $\thicksim$ greater than $\wedge$ which is in turn greater than $\vee$, in this grammar, because if you generate the parse tree, $\thicksim$ will be at the leaves.

  • 1
    $\begingroup$ There is no concept of priority in this grammar: it is just a set of rules for producing strings. It seems reasonable to view the strings generated by $S$ as disjunctive normal forms with, implicitly, the operator precedence that you give (and, bizarrely, where the only variable is $p$) but the grammar doesn't say anything like that. $\endgroup$ – David Richerby Feb 12 '14 at 9:26
  • 1
    $\begingroup$ @DavidRicherby Seeing grammars only as generating sets of strings is a particularly useless view of syntax. It is a lot more useful to see grammars as generating also sets of trees, the parse trees, and that is how they are always used in practice. As a generator of trees, this grammar precisely produces trees representing DNF (Disjunctive Normal Form) formulae corresponding to the generated strings when they are read with the suggested priority for operators. Without these priorities, the expression would not read as DNF. The answer is consistent, and the downvote is ill-founded. $\endgroup$ – babou Feb 13 '14 at 0:43
  • $\begingroup$ @DavidRicherby I think you need to review the concept of priority of the symbols in this grammar here, parse tree of this grammar will contain ∼ at the leaves, so it priority becomes greater. $\endgroup$ – abstractnature Feb 13 '14 at 2:00
  • 1
    $\begingroup$ @babou In David's defense, that is a result of attaching semantics to words along the syntax trees, not of the grammar itself. $\endgroup$ – Raphael Feb 13 '14 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.