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


5

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


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

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


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