Intereting Posts

Can someone provide the formal definition of the tangent line to a curve?
Poisson Integral is equal to 1
Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves?
Exact sequences of $SU(N)$ and $SO(N)$
How to prove gcd of consecutive Fibonacci numbers is 1?
In differential calculus, why is dy/dx written as d/dx ( y)?
linear least squares minimizing distance from points to rays – is it possible?
When can a pair of groups be embedded in each other?
$x^TAx=0$ for all $x$ when $A$ is a skew symmetric matrix
Real Numbers to Irrational Powers
Why do graph degree sequences always have at least one number repeated?
A conjecture about Pythagorean triples
Proving a trig infinite sum using integration
Triple integration, Spherical coordinates
There is a ray from each point of unbounded convex set that is inside the set.

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$.

How complicated is $\mathcal T$? Is it a context-free language?

Does the answer depend on the *fixed* number of variables? I guess not… If one removes the limitation of the number of variables (and somehow adapts the notions of context-freeness to play nice with this…), does the answer change? I guess it does…

- How can the following language be determined in polynomial time
- Any problem computable in $k$ memory slots can be computed with polynomials.
- $e^{e^{e^{79}}}$ and ultrafinitism
- At what point does exponential growth dominate polynomial growth?
- Why isn't NP = coNP?
- Is factoring polynomials as hard as factoring integers?

This question is a natural outcome of Doug’s recent question here.

- What is the simplest collatz like problem that is undecidable?
- What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?
- How can the following language be determined in polynomial time
- Computational complexity of least square regression operation
- Why are Hornsat, 3sat and 2sat not equivalent?
- Proving that language is not regular by pumping lemma
- Modern approaches to mathematical notation
- Algorithm to answer existential questions - Reduction
- finding right quotient of languages
- Are derivatives actually bounded?

For a fixed number of variables, it’s context free, regardless of the exact connectives used. To show this, we will construct a context-free grammar for the set of tautologies.

Let the number of variables be $n$. For each $f\colon \{0,1\}^n \rightarrow \{0,1\}$, there corresponds a non-terminal $S_f$ generating all formulas with truth table $f$. The starting symbol is $S_1$, where $1$ is the constant $1$ function.

For your connectives, here is the construction. For each projection function $p_i$, we add the production $$S_{p_i} \rightarrow x_i$$ ($x_i$ is a variable). For each $f$, we add the production $$S_f \rightarrow \lnot S_{1-f}.$$ For each $f_1,f_2$, we add the production $$S_{1-f_1(1-f_2)} \rightarrow S_{f_1} \Rightarrow S_{f_2}.$$

Now consider the case of an infinite number of variables. If there were a CFG for the set of all tautologies (with some fancy encoding), then you could decide whether a particular formula is a tautology in polynomial-time, so P=NP.

More to the point, suppose that the encoding we wish to use is strings in some appropriate (finite alphabet). If the language of all tautologies were context-free, then so would $\{ x_i \Rightarrow x_i : i \in \mathbb{N} \}$ (intersect with an appropriate regular language). It follows that the language of squares in the digits is context-free, which is false.

Yes, it’s context-free. A formula is a tree, which can be traversed with a stack. As we traverse, we are evaluating four things:

- x = 0, y = 0;
- x = 0, y = 1;
- x = 1, y = 0;
- x = 1, y = 1.

In effect, we are evaluating four “substantiated formulas” in parallel. A substantiated formula is one with variables replaced by 0 or 1.

Let’s get more precise and define the transition table. We assume that the formula is in pre-order, that is, operator before operands.

- The initial state:
- If the current symbol is “$\lnot$”, push onto the stack the symbol “($\lnot$, operator, ?, ?, ?, ?)” and go to the initial state.
- If the current symbol is “$\to$”, push onto the stack the symbol “($\to$, operator, ?, ?, ?, ?)” and go to the initial state.
- If the current symbol is “x”, go to the (0, 0, 1, 1) state.
- If the current symbol is “y”, go to the (0, 1, 0, 1) state.

- The (a, b, c, d) state:
- If the top symbol of the stack is “($\lnot$, operator, ?, ?, ?, ?)”, pop the stack and go to the ($\lnot$a, $\lnot$b, $\lnot$c, $\lnot$d) state.
- If the top symbol of the stack is “($\to$, operator, ?, ?, ?, ?)”, pop the stack, push “($\to$, first operand, a, b, c, d)”, go to the initial state.
- If the top symbol of the stack is “($\to$, first operand, e, f, g, h)”, pop the stack, go to the (e $\to$ a, f $\to$ b, g $\to$ c, h $\to$ d) state.

The (a, b, c, d) state is a template. There are actually 16 such states: the (0, 0, 0, 0) state, the (0, 0, 0, 1) state, the (0, 0, 1, 0) state, the (0, 0, 1, 1) state and so on.

Similarly, the third rule in the generic (a, b, c, d) state is a generic rule. There are 16 such rules, with (e, f, g, h) = (0, 0, 0, 0), (0, 0, 0, 1), and so forth.

The (1, 1, 1, 1) state has one extra rule:

- If the stack is empty, go to the accepting state.

OK, this program has a weak point as discussed in the second comment. Now let’s define a perfect version.

Assume two things: 1) The formula is in pre-order, and 2) there is a pair of parenthesis around each sub-formula.

Now, the transition table:

- start:
- if read = (, go to operator.

- operator:
- if read = ~, push (~, ?, ?, ?, ?), go to start.
- if read = ->, push (->, ?, ?, ?, ?), go to start.
- if read = x, push (ret, 0, 0, 1, 1), go to eval.
- if read = y, push (ret, 0, 1, 0, 1), go to eval.

- eval:
- if read = ), let the top element be (ret, a, b, c, d), pop, go to (a, b, c, d).

- (a, b, c, d):
- if read = ) and top = (~, ?, ?, ?, ?), pop, go to (~a, ~b, ~c, ~d).
- if read = ) and top = (->, e, f, g, h), pop, go to (e -> a, f -> b, g -> c, h -> d).
- if read = ( and top = (->, ?, ?, ?, ?), pop, push (->, a, b, c, d), go to operator.

- (1, 1, 1, 1) has one extra rule:
- if the stack is empty, accept.

Generalization of Yuval’s answer:

For any finite set $A$ and operations $o_i \colon A^2 \to A$ the language of expressions using elements of $A$ and infix operators $o_i$ that evaluate to fixed $a \in A$ is context-free. Here $A = \{0,1\}^n \to \{0,1\}$.

If you regard the expressions as trees not words, it will be a regular tree language (recognizable with finite tree automaton).

I remember an exercise in automata theory: the set of Boolean formulas (as words) using 0,1,$\vee$,$\wedge$,$\neg$,(,) evaluating to 1 is regular, provided that arbitrary answer is allowed when input has mismatched brackets.

As a consequence of this there should exist a regular language $L$ such that the set of tautologies is $L \cap R$ where $R$ is the context-free language of all well-formed formulas (tautologies or not).

- Evaluating $\sum\limits_{k=1}^{\infty}\frac1{(3k+1)(3k+2)}$
- Questions of an exercise in Lebesgue integral
- How do you use the BBP Formula to calculate the nth digit of π?
- Let $a_{i} \in\mathbb{R}$ ($i=1,2,\dots,n$), and $f(x)=\sum_{i=0}^{n}a_{i}x^i$ such that if $|x|\leqslant 1$, then $|f(x)|\leqslant 1$. Prove that:
- Composition of two reflections (non-parallel lines) is a rotation
- Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete
- Power series of a function
- Are locally compact Hausdorff spaces with the homeomorphic one-point compactification necessarily homeomorphic themselves?
- Are there vector bundles that are not locally trivial?
- In the Sorgenfrey plane, is an open disc homeomorphic to an open square?
- Prove that the product of primes in some subset of $n+1$ integers is a perfect square.
- linear subspace of dual space
- How to show that $1 \over \sqrt{1 – 4x} $ generate $\sum_{n=0}^\infty \binom{2n}{n}x^n $
- Quadratic Polynomial factorization
- Gateaux and Frechet derivatives on vector valued functions