0
$\begingroup$

Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$ consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$. Prove that FSTs are not closed under this operation $\Delta(T_1,T_2)$.

What I have tried is to create two FSTs $T_1, T_2$ (as 5 tuple functions of form $(Q, \Sigma, \Gamma, \delta, s, γ)$ where $\Sigma$ - input symbols, $\Gamma$ - output symbols, $δ\colon Q \times \Sigma → Q$ transition function, to prove that the language $S = \{ w \mid T_1(w) \neq T_2(w) \}$ is not regular. I am having trouble creating the two FSTs. Especially defining the transition functions for the two FSTs. Any help with this is appreciated.Pretty much what I am trying to prove is there are two FST's $T_1$ and $T_2$ such that the language $L = \{w \mid T_1(w) \ne T_2(w)\}$ is not regular. To prove this, what I want to do is create the two FST's $T_1$ and $T_2$. I am not sure on how to define a 6-tuple FST. Especially coming up with the transition functions for the two FSTs

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Welcome to CS.SE! We do not want to just do your exercise for you; we want you to gain understanding. However, you haven't given us much to work with and it's hard to tell what your underlying problem is, so we can not begin to help (see here for a relevant discussion). You say you're having trouble, but what specifically is your confusion/uncertainty? Can you try to formulate an answerable question that will be useful to others in the future and that doesn't just involve telling you how to do your exercise for you? $\endgroup$
    – D.W. ♦
    Commented Nov 11, 2015 at 7:10
  • 1
    $\begingroup$ For example, can you identify some specific conceptual issue you're uncertain about and edit your post to ask about it? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$
    – D.W. ♦
    Commented Nov 11, 2015 at 7:10
  • 5
    $\begingroup$ What do you mean by "FST's are not closed under this operation"? $T_1$ and $T_2$ are functions, but $\Delta(T_1,T_2)$ is a language, not a function. $\endgroup$
    – J.-E. Pin
    Commented Nov 11, 2015 at 10:57
  • $\begingroup$ Thank you for the edit. However, I'm afraid the question still suffers from the problem that I articulated earlier: you're basically just asking us to do your exercise for you. In addition, you still have not addressed the issue that J.-E. Pin identified. I will leave it for community to determine whether the question meets our standards in its current form. Any community votes? $\endgroup$
    – D.W. ♦
    Commented Nov 11, 2015 at 21:23

1 Answer 1

Reset to default
2
$\begingroup$

It is probably a better idea first to concentrate on the complement, i.e., the equality language $\{ w\in \Sigma^* \mid T_1(w) = T_2(w) \}$.

Also, simple FST's will do, as even for morphisms $h_i: \{a,b\} \to \{1\}^*$, $\{ x\in \{a,b\}^* \mid h_1(x) = h_2(x) \}$ need not be regular.

And I want to add that it has been shown that $\Delta(T_1,T_2)$ is always context-free.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You had $w\in\{a,b\}^*$. I changed it to $x$. $\endgroup$
    – Rick Decker
    Commented Nov 12, 2015 at 2:57
  • $\begingroup$ @RickDecker Thanks. The first language had the same problem! $\endgroup$
    – Hendrik Jan
    Commented Nov 12, 2015 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.