[Solved]: What Do Logical Operators In a Grammar Mean?

Problem Detail: 

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.

Asked By : navlag

Answered By : vonbrand

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$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21539

3.2K people like this

 Download Related Notes/Documents