Context Free Grammar and regexp

Question

I want to construct a Context Free Grammar which will generate all the strings which have at least one occurrence of each of character of M, N, P, Q (they are not neccesserily different for example they can be A A A A) and possibly infinite occurrence of A, C, G, T (a few examples are MNPQA, MNAAPQ, MNPQ, MAPGNQC, etc.). Using regexp I can get these strings MNPQ[ACGT]* and all possible permutations of this. The question is can we construct a context free grammar or only one regexp which will generate all the strings I want ?

Answer 1

I suppose you are working on the alphabet $\Sigma= \{A, C, G, T\}$. Then the set of strings you are looking for is $$L =\Sigma^*M\Sigma^* \cap \Sigma^*N\Sigma^* \cap \Sigma^*P\Sigma^* \cap \Sigma^*Q\Sigma^*$$ Since $L$ is an intersection of regular languages, it is itself regular. Therefore it can represented by a regular expression. However, this expression depends on the respective values of $M,N,P,Q$ and can be quite large. Just to give you an idea, if $M = A, N = C, P = G$ and $Q = T$, then the minimal automaton of $L$ has 16 states and $L$ is the union of $\Sigma^*M\Sigma^* N\Sigma^* P\Sigma^* Q\Sigma^*$ and all 23 other regular expressions obtained by permuting $M,N,P,Q$.