Skip to main content
5 votes
Accepted

Can lambda-calculus be used for knowledge representation?

The λ-calculus was invented to be a logic and foundation of mathematics (1-4). The most well-known logic to use λ-calculus for formulae (as opposed to proofs in the Curry-Howard ...
Martin Berger's user avatar
5 votes

Does there exist an context free language L such that L∩L^R is not context free?

Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$. In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera. Note that we can get really fun things: For $ L ...
Hendrik Jan's user avatar
  • 30.7k
4 votes

Why has it taken so long to prove that P != NP?

Sometimes a short and easily verifiable proof takes a long time to discover. This may be due to several reasons. Maybe the general consensus in the research community is that the claim is probably not ...
Ilkka Törmä's user avatar
4 votes

Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?

You are on your way to discovering the Curry-Howard correspondence.
Andrej Bauer's user avatar
  • 30.9k
3 votes

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

Your language consists of all words starting with $0$ and ending with $1$.
Yuval Filmus's user avatar
2 votes

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

Your solution depends on $n$. In this case the $n$ in the formulation of the language is not a constant, but a variable ranging over the positive integers $n\ge 1$. So we need strings of the form $0^n ...
Hendrik Jan's user avatar
  • 30.7k
2 votes
Accepted

Why has it taken so long to prove that P != NP?

Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid ...
Steven's user avatar
  • 29.5k
1 vote

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

Your language is regular and can be rewritten as $$ L = {0\Sigma^*1} $$ (start with 0 end with 1)
rzv09's user avatar
  • 13
1 vote

Where do transformational grammars stand in the Chomsky Hierarchy?

I was taught in linguistics class that Chomsky abandoned his original arbitrary transformations after they were found to produce Turing completeness. See e.g. the Oxford Handbook of Linguistic ...
reinierpost's user avatar
  • 5,746

Only top scored, non community-wiki answers of a minimum length are eligible