Questions tagged [computational-linguistics]
The computational-linguistics tag has no summary.
24 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
0
answers
45
views
What is the general theory behind finding similar sequences of symbols, such as for rhyming multiple syllables?
I am considering how to create a rhyming dictionary, provided I have a database of phonetic representations of words, and about 1 million words phonetically transcribed.
Sidenote: I also have phonetic ...
1
vote
2
answers
467
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 ...
1
vote
0
answers
76
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 ...
-6
votes
3
answers
362
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 ...
-1
votes
2
answers
3k
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 ...
2
votes
3
answers
795
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 x1^n$ | 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 ...
2
votes
0
answers
139
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 ...
1
vote
0
answers
130
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 ...
3
votes
0
answers
285
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 related ...
1
vote
0
answers
174
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 ...
2
votes
0
answers
41
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/...
6
votes
1
answer
327
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
vote
1
answer
180
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 ...
5
votes
1
answer
444
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
vote
0
answers
176
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 ...