# Questions tagged [computational-linguistics]

The tag has no usage guidance.

23 questions
Filter by
Sorted by
Tagged with
1 vote
394 views

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

By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
• 11
1 vote
33 views

### Are there known algorithms for generating abbreviations from a (sequence) of words (similar to hyphenation)

I'm currently developing a custom UI layout library. At the moment a user of that library should supply strings for UI labels in a format that allow for subsequent shortening of those labels, so that ...
• 111
260 views

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

A question that answers itself. If P=NP could be proved in a formal language, then surely it would be as easy to verify the proof as it would be to discover/derive it? Couldn't a program just quickly ...
2k views

### Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$

I tried many grammars and so far I got this one: \begin{align} &S \to aXbZ \mid abc \\ &XZ \to Ybcc \\ &Xb \to bX \\ &bY \to Yb \\ &aY \to aa \mid aaX \end{align} Is my grammar ...
623 views

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

I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the ...
• 21
104 views

### What's the meaning of linguistics?

In the programming language theory world, there are two important terminologies, i.e syntax, and semantics. I can understand these two terminologies: syntax is about sentence's structure (e.g. a valid ...
• 295
1 vote
112 views

### What are open problems in computer science? [closed]

I should prepare some paper for a colloquium (kinda student-task) and it should cover the following points: (1) at least one notable discovery in theoretical informatics (or computer science) (2) at ...
250 views

### Why is part of speech tagging is closely related to word sense disambiguation?

It's written here Word Sense Disambiguation: A Structured Learning Perspective: 2.1 Basics of Word Sense Disambiguation ...the POS is usually provided before WSD. POS tagging is closely ...
• 177
1 vote
118 views

### Combining Computer Science and Humanities

I currently hold a bachelors in Computer science and a masters in Art History. I really want to combine the two and I know of Digital Humanities but I'm not completely aware of where Digital Humanists ...
• 11
19 views

### Induction / (machine learning) of Resource Grammars for Grammatical Framework?

Grammatical Framework is based in Abstract Categorial Grammars. It is known that Combinatory Categorial Grammars have grammar induction/learning capabilities see e.g. https://link.springer.com/article/...
• 1,401
276 views

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

I am reading http://okmij.org/ftp/gengo/applicative-symantics/AACG1.pdf and there is defined language TL (see last row in the table on page 4). It seems to me from this definition of TL, that lambda ...
• 1,401
1 vote
133 views

### Where do transformational grammars stand in the Chomsky Hierarchy?

From what I understand, natural language are too complicated to be generated by a context-free grammar, yet parsing a context-sensitive grammar is too computationally demanding for our brain to be ...
• 111
389 views

### Can lambda-calculus be used for knowledge representation?

Natural language semantics (in computational linguistics) uses lambda terms for expressing the semantics of natural language sentences. There is vast literature about combinatorial categorial grammars ...
• 1,401
1 vote
151 views

### Second-order Markov text generation?

Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which ...
• 469
1 vote
27 views

### N-Grams - how to predict further into the future and how far can we predict?

I am using N-Grams to predict future character input. For n+1, it performs really well. I've been looking, but I have not been able to find any information on what the feasible maximum distance into ...
• 183
1 vote
16 views

### Evaluation of annotation

I'm doing a research on NLG systems. I need to annotate my corpus (~6 million words) automatically. My algorithm works well and I want to calculate Cohen's Kappa. What I cannot understand is the ...
168 views

### Algorithm to find pronounciation rules

Suppose that you have a large dictionary with spellings and pronounciations of foreign words, and you want to find a set of pronunciation rules. They should have the simplest form: a sequence of ...
• 213
38 views

### How can feature structures be applied to text summarization?

I'm looking for innovative ways to create text summaries and I was wondering whether feature structures can be used for such a task. Is it possible to create subsume and unification methods that ...
• 111
1k views

### Is English Recursively enumerable? [closed]

The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive ...
• 203
4k views

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

In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$. I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use ...
952 views

### Correct term for “string consisting of words”

In a paper I am writing I want to make distinction between (1) string consisting of any characters and (2) string consisting of a chain of words from known language, with possible delimiters. My ...
38 views

### Trying to tag parts of a word and keep track of any changes that happen to those parts

I'm a researcher working with a language that has gone through phonological changes through time. I would like to tag parts of a word (i.e. prefix, stem, suffix) and then apply those phonological ...
• 121