# How to show that a set does not contain a specific string

If I have actually a set $S$ specified as the tiniest set $S$ over an alphabet $A=\left\{ \star, \urcorner,(,), a_0,a_1, \dots \right\}$ ($S\subseteq \cup_{k \in \mathbb{N}} A^k$) enjoyable:

$\bullet \ a_0, a_1, \ldots$ $\in S$

$\bullet$ if $\alpha \in S$ after that $( \urcorner \alpha) \in S$,

just how can I after that show as an example that $( \alpha \urcorner )$ or $\alpha ()$ is not in the recursively specified set $S$, where $\alpha$ is some component of $S$ (or perhaps $S\subseteq \cup_{k \in \mathbb{N}} A^k$, for better generalization). Certainly I can "see" that this holds true, yet just how can I confirm it?

Possibly due to the fact that it appears so very easy to see that strings like the above can not remain in $S$ I can not up with an evidence. (Of training course, if $\star \alpha$ remained in $S$, with ease it would certainly be clear, that $S$ woulsn't be the tiniest set any longer, yet just how would certainly I after that confirm this?)

1
2022-06-07 14:33:52
Source Share

Added Remark: This is a remedy to the previous manifestation of the inquiry, which was fairly various (it asked one to show that no word of form $\star\alpha$ remains in the set). This is not a remedy of the transformed inquiry!

It is noticeable, and also does not call for evidence (unless, strangely, it is required that you confirm it).

What do we suggest by "smallest set $S$"? In the context of this sort of definition, it suggests the junction of all the collections pleasing your 2 bulleted problems.

Currently allow $W$ be the set of all words over the alphabet which contains every little thing other than the $\star$, Then $W$ clearly pleases the bulleted problems. It adheres to by the definition of $S$ that $S \subset W$, given that $W$ is just one of the collections that was converged to make $S$. And also it is clear that no word of the kind $\star\alpha$ remains in $W$.

Statement around transformed inquiry The approach of an evidence does not transform a lot for the transformed inquiries. (But if the inquiry adjustments once more, the approach could need to transform). As an example, consider the set $Z$ of words that do not end with $()$ or with $($. It is clear that if $\alpha$ remains in $Z$, after that the string generated by the 2nd bulleted problem remains in $Z$. So $Z$ is just one of the collections converged to generate $S$. This indicates that $S$ does not have any kind of string of form $\alpha()$.

0
2022-06-07 14:57:07
Source