Fred Jefferson's user avatar
Fred Jefferson's user avatar
Fred Jefferson's user avatar
Fred Jefferson
  • Member for 4 years, 5 months
  • Last seen more than 1 year ago
3 votes
1 answer
88 views

Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

3 votes
1 answer
324 views

Skyline problem with triangular buildings

2 votes
1 answer
224 views

Asymptotic height of d-ary heap

2 votes
1 answer
282 views

The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem

2 votes
1 answer
224 views

prove that context free languages are closed under the $\circ$ operation

2 votes
1 answer
122 views

Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free

2 votes
2 answers
159 views

How can we show that P is not closed under taking all long prefixes?

1 vote
2 answers
70 views

Show that the Hamming distance of $wx$ and $xw$ cannot be 1

1 vote
1 answer
74 views

Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?

1 vote
1 answer
79 views

is there a non-context free language A such that A1 is context free?

1 vote
1 answer
134 views

a halting turing machine

1 vote
0 answers
273 views

show that neither $S$ nor $\overline{S}$ is turing recognizable

1 vote
1 answer
754 views

extending bellman ford to find shortest weight paths with no repeating vertices

1 vote
0 answers
20 views

an NFA whose corresponding DFA has at least $2^n - \alpha$ reachable states [duplicate]

1 vote
2 answers
508 views

finding a greedy algorithm that maximizes total energy of fruits subject to expiry dates

1 vote
1 answer
84 views

uniformly distributed edge weights in an MST

1 vote
1 answer
42 views

if $RA$ is context-free, is $A$ context-free?

1 vote
1 answer
399 views

determining whether a context-free language is regular

1 vote
1 answer
212 views

prove that there does not exist a Turing machine with a particular property

0 votes
1 answer
105 views

Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

0 votes
1 answer
68 views

determining the relationship between two regular languages using the myhill nerode theorem

0 votes
1 answer
60 views

prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set

-1 votes
1 answer
78 views

prove $A$ is context-free