The Gateway to Computer Science Excellence
0 votes
10 views
Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the strings $xz$ and $yz$ is a member of $L;$ otherwise, for every string $z,$ we have $xz\in L$ whenever $yz\in L$ and we say that $x$ and $y$ are $\text{indistinguishable}$ by $L.$ If $x$ and $y$ are  indistinguishable by $L,$ we write $x ≡L y$. Show that $≡L$ is an equivalence relation.
A $\text{palindrome}$ is a string that reads the same forward and backward.
in Theory of Computation by Veteran (52.9k points) | 10 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,170 answers
193,841 comments
94,047 users