1
$\begingroup$

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example simple grammars $$ S \rightarrow XY \\ X \rightarrow aXb | ab \\ Y \rightarrow Ya | a$$ and also $G_2$ is $$ S \rightarrow YX \\ X \rightarrow bXa | ba \\ Y \rightarrow Ya | a$$ (I know these are CF grammars but intersection of them is not CF so I was trying to create unrestricted grammar for $G_1 \cap G_2$) so I change these grammars like below to generate $G'$ that is an unrestricted grammar for $G_1 \cap G_2$. $$ S \rightarrow X'Y' \\ X' \rightarrow AX'B | AB \\ Y' \rightarrow Y'A | A \\ BXA \rightarrow X \\ BA \rightarrow X \\ A \rightarrow Y \\ YA \rightarrow Y\\ YX \rightarrow S'$$ but there is two problem that I will forget string that will be accepted because finally the only thing will remain is $S'$ and another problem is that if I have $\lambda$ in the right side of grammar I can't move it to the left side for unrestricted grammar. is my approach true for solving this problem? and what is the idea of solving this?

Edit (complete some part it)

I think after accepting by grammar $G_1$ we can create copy of accepted string by following steps, imagine $aabba$ is accepted by $G_1$ it means that I have $AABBA$ now I can add following rules for every $t \in Terminals$ $$ T \rightarrow T'T'' $$ so $AABBA$ will be $A'A''A'A''B'B''B'B''A'A''$ and now I can define following rules for every $t,r \in Terminals$ $$ T''R' \rightarrow R'T'' $$ now every variable that is the mirror of a terminal with single quotation will jump over variables with double quotation and the result will be $A'A'B'B'A'A''A''B''B''A''$ now I can work with variables with single quotation and after they disappear add rules to convert double quotation variables to terminals, for every $t \in Terminals$ $$ T'' \rightarrow t $$ now just needed to proof that this will not accept string that is not in $L(G_1) \cap L(G_2)$ that I thinks its not complicated and the other thing is that I still don't know what should I do with $\lambda$ in right side of grammar rules.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ How do you know there is a solution at all? $\endgroup$ – reinierpost Jan 14 '18 at 10:24
  • $\begingroup$ @reinierpost proving that there is a solution is equivalent to the solution of the problem. the only way to show that there is a solution to the problem is a constructive proof. I don't think there is existence proof for showing that there is a solution to a problem with a specific method in this case. $\endgroup$ – Karo Jan 14 '18 at 12:07
  • $\begingroup$ What I mean is: you could first try to prove that there is no solution. I'm no expert, but I wouldn't be surprised if this is undecidable. $\endgroup$ – reinierpost Jan 14 '18 at 12:27
  • $\begingroup$ @Karo "the only way to show that there is a solution to the problem is a constructive proof." -- No, that's not necessary. $\endgroup$ – Raphael♦ Jan 14 '18 at 14:13
  • $\begingroup$ "I don't want to use Turing machine or etc" -- Why? Not every model is well suited for every proof. My guess is that if you prove closure against intersection using grammars, you'll be repeating much of the simulation of machines with grammars. $\endgroup$ – Raphael♦ Jan 14 '18 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.