11
votes
Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
Your approach does not work: you can't force all the variables to "double" at once using only context-free rules.
As the other answers show, your effort is futile: $L$ is not context-free, so there ...
- 72k
6
votes
Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
A language which is a subset of $a^*$ is known as a unary language. There is a complete classification of unary languages which are context-free. In particular, if $L$ is a unary language then the ...
- 275k
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 ...
- 8,308
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 ...
- 29.8k
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 ...
- 288
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$.
- 275k
2
votes
Accepted
Algorithm to find pronounciation rules
Broadly, I can see two possible approaches: machine learning, or data mining
Machine learning
You could look into using machine learning to learn a transducer that transforms the input sequence (the ...
D.W.♦
- 156k
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 ...
- 28.2k
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 ...
- 29.8k
2
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.
- 30k
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 ...
- 5,359
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)
- 13
Only top scored, non community-wiki answers of a minimum length are eligible