2
votes
1answer
213 views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
2
votes
1answer
236 views

Detecting cycles in off-line Turing machines

Let $M$ be an off-line Turing machine over the input alphabet $\{0,1\}^{*}$, that uses only one working tape in addition to the input tape. Construct a Turing machine $M'$, such that: $L(M) = ...