All Questions
Tagged with complexity-theory formal-languages
14 questions with no upvoted or accepted answers
3
votes
0
answers
183
views
Hopcroft & Ullman: 1969 vs. 1979
How do the 1969 and 1979 books by Hopcroft & Ullman compare? Was the 1969 book an earlier version of the 1979 book?
1969: Formal Languages and their Relation to Automata
1979: Introduction to ...
- 131
3
votes
0
answers
29
views
How to model grammar ambiguity
Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings.
Practically, ...
- 361
1
vote
0
answers
16
views
Critical Pair Determination in Knuth Bendix
In the Knuth Bendix completion algorithm, how does one identify all the critical pairs for an abstract term rewriting system? Does one have to iterate through each rule, and then identify which pairs ...
- 11
1
vote
0
answers
37
views
About infinite languages in RE and coRE
Let $L \in RE$. Then $L$ might be finite or infinite.
I assume this is also true for $coRE$.
But, if I have a language $L \notin RE$, it necessarily means that $L$ is infinite, am I correct?
Also, if $...
- 47
1
vote
0
answers
38
views
How to show a language is not recursive, without using reductions?
I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
- 142
1
vote
0
answers
138
views
Proving existence of a language $L\in DTIME(n^{\log n})$ which is not in $Avg-P$
I'm struggling with the following question:
Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{...
- 11
1
vote
0
answers
241
views
Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?
One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
- 1,401
1
vote
0
answers
58
views
Reduction from L to Htm
I'm trying to prove a problem that a friend sent me, he is saying that my solution is not good and I wanted to ask if he is correct and im wrong , and if so why?
here is the questions:
$L=\{<M>|...
- 133
0
votes
0
answers
93
views
Efficient Algorithm To Find A Path Which Covers Maximum Area Along Polygonal Perimeter For Surveillance Application
In the context of surveillance, I am working on a project where the goal is to find an algorithm that determines a path along a polygonal area, connecting a root node to a target node, while ...
- 3
0
votes
0
answers
41
views
Complement of a language definition
Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$.
I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M ...
- 47
0
votes
0
answers
46
views
Lower bound for $a^kb^k$ in one-tape TM
For the language
$ L= \{a^kb^k | k \geq 0 \} $
How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?
- 368
0
votes
0
answers
205
views
how to write a language for context-free grammar generates the empty string?
How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
0
votes
0
answers
58
views
One-way-function based on Friedberg numberings
A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
- 109
0
votes
0
answers
149
views
Proving P and NP on problems formulated as languages
To prove that a certain problem is in P we have to give an algorithm that decides or solves it in polynomial time. To prove that a problem is in NP an algorithm must exist so that it can check whether ...
- 1