11

$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 $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \...


10

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 can be no such grammar. For reference, context-sensitive rules allow you to control the "doubling". Idea: move markers through the sentence; only with the ...


6

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 following are equivalent: $L$ is context-free. $L$ is regular. There exists $m$ such that $a^n \in L$ iff $a^{n+m} \in L$. There exist $m_1,m_2$ and subsets $S_1 \...


5

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 approach) is HOL (= Higher-Order Logic). The most well-developed implementation of HOL is Isabelle/HOL (5). To the extent that you believe logic can represent ...


5

As D.W. said, the task of classifying words as noun, verb, etc. is called part-of-speech tagging: The machine learning algorithm typically used for this purpose is the Log-Linear Model (aka. Maximum-Entropy, in short MaxEnt). It is actually pretty straightforward: Assume you read the sentence sequentially (left to right, or right to left) Let $h$ be the ...


5

This is a standard problem in Natural Language Processing (NLP). Classifying whether each word is a noun, verb, etc., is known as "part-of-speech tagging". Searching on that term should turn up a lot of information about how to do that. If you want to tag the words in some other way, you might be able to use other tagging algorithms. They generally use ...


4

If definition (1) is intended for any sequence of characters, I would simply call it string as you suggest, but I would call it word or lexeme if it is intended to be words of a language. Regarding definition (2), it depends again on what you are expecting to consider. If it is any sequence of words, usually meaningless, with a variety of separators, the ...


3

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 true, and most people who work on it are trying to prove the converse. Maybe it's believed to be too difficult for current techniques, and most researchers ...


3

Your language consists of all words starting with $0$ and ending with $1$.


2

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 letters in the word) to the output sequence (the pronunciation). This approach doesn't try to find an explicit set of rules; it just tries to find a method ...


2

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 x 1^n$ for any $n\ge 1$, and any $x\in\Sigma^*$. In general that would not be possible with a FSA, it cannot count and compare the numbers of $0$'s and $1$'s, ...


2

You are on your way to discovering the Curry-Howard correspondence.


1

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 then there must exist an algorithm $B$ that decides whether such a short proof exists. Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$. There are ...


1

Your language is regular and can be rewritten as $$ L = {0\Sigma^*1} $$ (start with 0 end with 1)


1

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 Interfaces, p. 543; I am unable to locate the original reference. He subsequently developed a formalism with more restricted transformations; the version I was taught ...


1

You can use sequence alignments with a suitable score. You then get something like this: $\qquad\displaystyle \begin{array}{cccccc} r & e & p & e & a & t & e & d \\ r & - & p & e & - & t & e & - \end{array}$ Now, if you have marked the original word, you can read off that -- according to your ...


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