I have the following CFG questions which I am having a hard time getting my head around, I don't have any answers for them so I have no way of knowing if ive done them right or not (even though im pretty sure they're wrong) any help with reviewing my results would be much appreciated.
$P_1 = (S \rightarrow 0S |1A|\epsilon, A \rightarrow 0A|1S)$
$P_2 = (S \rightarrow S1 |A0|\epsilon, A \rightarrow A1|S0)$
1.Show that the language $L(G_1)$ is regular.
A regular expression shows that the language is regular as far as I know. Everytime I make derivatives of the CFG i just get variations of $010$ but I can see that it can finish with a 1 so my guess at the language is, $(0+1)(0|1)^*$.
2.Give strings of length 4 that belong to $L(G_1) \cap L(G_2)$
$L(G_2)$ is the complement of L(G_1) so the strings of length 4 accepted would be, $0000, 0101, 1001, 1010, 1100$
3.draw a dfa with at most 4 states for $L(G_1) \cap L(G_2)$
Considering the strings accepted the dfa diagram for this question will be the typical 4 state dfa that accepts even strings. https://i.stack.imgur.com/LxihX.jpg
4.draw a dfa with at most 4 states for the complement $L(G_1) \cap L(G_2)$
This dfa diagram will be the same as the previous but with the non final states becoming final states and the final state becoming non final
A derivation in $G_1$ can stop only when the production $S\to\epsilon$ is applied. This means that if the derivation ever uses $S\to 1A$, it must eventually use $A\to 1S$, so as to have an $S$ to delete. Here are some possible derivations:
$$\begin{array}{ccc} S&\Rightarrow^{n_1}&0^{n_1}S&\Rightarrow&0^{n_1}1A&\Rightarrow^{n_2}&0^{n_1}10^{n_2}A&\Rightarrow&0^{n_1}10^{n_2}1S&\Rightarrow^{n_3}&0^{n_1}10^{n_2}10^{n_3}S\\ \Downarrow&&\Downarrow&&&&&&\Downarrow&&\Downarrow\\ \epsilon&&0^{n_1}&&&&&&0^{n_1}10^{n_2}1&&0^{n_1}10^{n_2}10^{n_3} \end{array}$$
Here $n_1,n_2$, and $n_3$ can be any non-negative integers, and a bit of thought should convince you that this diagram shows every possible derivation that uses the productions $S\to 1A$ and $A\to 1S$ just once each. Those derivations evidently suffice to generate all words of the forms $0^n$ for $n\ge 0$ and $0^{n_1}10^{n_2}10^{n_3}$ for $n_1,n_2,n_3\ge 0$. We can extend the derivation to the right by applying $S\to 1A$ again, then $A\to 0A$ some $n_4\ge 0$ times, then $A\to 1S$; if we then apply $S\to 0S$ some $n_5\ge 0$ times followed by $S\to\epsilon$, we’ve generated all words of the form $0^{n_1}10^{n_2}10^{n_3}10^{n_4}10^{n_5}$. If you continue this analysis, you should see that we can produce every word that contains an even number of $1$s. It’s not clear from the question whether you’re just supposed to identify the language, or whether you’re supposed to prove the correctness of your identification; the latter is substantially more difficult.
This language is regular, but it certainly isn’t represented by the regular expression $(0+1)(0\mid 1)^*$: that regular expression, which combines two different notations and should be written either $(0\mid 1)(0\mid 1)^*$ or $(0+1)(0+1)^*$, represents every non-empty word. In fact $L(G_1)$ is the regular language represented by the regular expression $(0^*10^*1)^*0^*$, among other possibilities. (Alternatively, you can demonstrate that it’s regular by designing a DFA that accepts precisely those words over $\{0,1\}$ that contain an even number of ones.)
$G_2$ does not generate the complement of $G_1$. For each $x\in\{0,1\}^*$ let $\overline x$ be the string that results from replacing each $0$ in $x$ by $1$ and each $1$ in $x$ by $0$. Let $x^R$ be the reversal of $x$. $G_2$ interchanges $0$ and $1$ and generates strings from right to left instead of from left to right, so $x\in L(G_0)$ if and only if $\overline x^R\in L(G_1)$. Now $\overline x^R\in L(G_1)$ if and only if $\overline x^R$ has an even number of ones, which is the case if and only if $\overline x$ has an even number of ones, which, finally, is the case if and only if $x$ has an even number of zeroes. Thus, $L_2(G)$ is the set of binary strings having an even number of zeroes, and $L_1(G)\cap L_2(G)$ is the set of binary strings having an even number of ones and an even number of zeroes. Thus, the set of words in $L(G_1)\cap L(G_2)$ of length $4$ is
$$\{0000,0011,0101,0110,1001,1010,1100,1111\}\;.$$
Your DFA for $L(G_1)\cap L(G_2)$ would be correct if you replaced the input labels $a$ and $b$ by the correct labels $0$ and $1$, and your answer to the fourth question is correct.