Articles of formal systems

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by listing all strings in lexicographic order and testing which belong to the language, but I would prefer some more tractable method.

What is the minimal axiomatization of a set of structures?

I wonder what the minimal axiomatization of a set of structures mean? I came across this term from Wikipedia: For a theory $T\in A,$ let $F(T)$ be the set of all structures that satisfy the axioms $T$; for a set of mathematical structures $S$, let $G(S)$ be the minimal axiomatization of $S$. We can then […]

Can the Negation of a Conditional Implying the First Atomic Proposition Get Proven in Around 50 Steps?

The following uses Polish notation with the following definition for meaningful expressions. All lower case letters are meaningful expressions. If $\alpha$ is a meaningful expression, then so is N$\alpha$. If $\alpha$ is a meaningful expression, if $\beta$ is a meaningful expression also, then C$\alpha$$\beta$ is a meaningful expression. The axioms are Ax1 CxCyx Ax2 CCxCyzCCxyCxz […]

Given an axiom in a formal system, can we always find another formal system in which this axiom is a theorem?

As an example, when set theory was created, it seems people tried to write the mathematical concepts they had using set theory, I guess that after this, what were previously axioms became theorems in set theory. I’ve made a silly example: Suppose we have $aRa$ as an axiom. I guess that we could find a […]

Why is it hard to parse unambiguous context-free grammar in linear time?

From this question, I gather that whether unambiguous CF grammar can be parsed in linear time is an open problem. I’d like to know what the major roadblocks to achieve this are. That is, what made the attempts to produce such a parser fail ?

Why can't we use memoization to parse unambiguous context-free grammars in linear time?

This is a follow-up question to Why is it hard to parse unambiguous context-free grammar in linear time? I know that Parsing Expression Grammars (PEG) can be parsed in linear time using a packrat parser. Those parser use memoization to accomplish the linear time complexity: basically each non-terminal can be “expanded” at most once at […]

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where each terminal appears 0 or 2 times? EDIT: Solving this may give interesting extension to “Restricted read twice BDDs and […]

Is it possible to formalize all mathematics in terms of ordinals only?

Our experience shows that all finitary mathematical objects could be encoded using the natural numbers, and all operations on those objects could be expressed in terms of a few basic operations on numbers: the successor operation, addition and multiplication. As far as I understand, this is not a theorem in the strict sense (because the […]

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?

natural deduction: introduction of universal quantifier and elimination of existential quantifier explained

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then $\phi_1\dots\phi_n\vdash\phi$, often abbreviated by $\Gamma\vdash\phi$, is called a sequent. Can somebody please explain to me the following two inference rules? Introduction of the universal quantifier. $$ \begin{array}{c} […]