Some concepts for finding CFG or finite state automata

Question

1. Given the information that L is a context-free language, is there any case that there is no algorithm to construct a context-free grammar for L? Any example?

2. Given the information that L is a regular language, is there any case that there is no algorithm to construct a finite state automata for L? Any example?

Answer 1

Given a recursively enumerable language $L$ and the information that $L$ is regular [resp. context-free, context-sensitive, recursive], there is no algorithm to construct a finite automaton [resp. a context-free grammar, a context sensitive grammar, a total Turing machine] for $L$.

Let $A$ be an alphabet and let $u, v \in A^*$. Then $u$ is said to be a superword of $v$ if there exist some words $u_0, \ldots, u_n, v_1, \ldots, v_n$ such that $v = v_1 \cdots v_n$ and $u = u_0v_1u_1v_2 \cdots v_nu_n$. For instance, $caccbaca$ is a superword of $abc$. Given a language $L$ on $A^*$, let $S(L)$ be the language of all words that are superwords of some word in $L$. The following result is an easy consequence of the fact, due to Higman [1], that the order on $A^*$ defined by $u \leqslant v$ iff $v$ is a superword of $u$, is a well-quasi-order.

Theorem. For each language $L$, $S(L)$ is a regular language.

Now, if $A$ is nonempty, there is no algorithm that, given a recursively enumerable language $L$, computes a total Turing machine (and hence of course, a finite automaton) for $S(L)$. Otherwise, one would be able to decide whether $S(L) = A^*$, which is equivalent to decide whether $L$ contains the empty word. But by Rice's theorem, this property is undecidable.

[1] G. Higman, Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society 2 (1952) 326–336.