# Tag Info

### 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 ...
Accepted

### Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages. Suppose $L$ is context-free. The pumping lemma says there exists some integer ...

### 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 ...
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 ...

### 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 ...

### 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$.
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 ...
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 ... 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. 1 vote 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 ... 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)