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

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

3 votes
1 answer
315 views

Skyline problem with triangular buildings

2 votes
1 answer
222 views

Asymptotic height of d-ary heap

2 votes
1 answer
281 views

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

2 votes
1 answer
218 views

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

2 votes
1 answer
104 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
157 views

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

1 vote
2 answers
67 views

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

1 vote
1 answer
71 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
76 views

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

1 vote
1 answer
131 views

a halting turing machine

1 vote
0 answers
262 views

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

1 vote
1 answer
678 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
484 views

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

1 vote
1 answer
83 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
373 views

determining whether a context-free language is regular

1 vote
1 answer
196 views

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

0 votes
1 answer
96 views

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

0 votes
1 answer
63 views

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

0 votes
1 answer
56 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
77 views

prove $A$ is context-free