onA language L is called slithy if it contains at least two strings and has the following property:For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of yand inserting it at the start of x is also in L.For example, if L contains aaa and baaba, then it must also contain the string baaa.Prove by contradiction that every slithy language contains two strings of the same length.

Answered: on A language L is called slithy if it…

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

on
A language L is called slithy if it contains at least two strings and has the following property:
For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of y
and inserting it at the start of x is also in L.
For example, if L contains aaa and baaba, then it must also contain the string baaa.
Prove by contradiction that every slithy language contains two strings of the same length.

Expert Solution

Step 1

Let's imagine there's a slithy language L that has two strings x and y with differing lengths, say Ixl Iyl. Let's also claim that L has both of these strings. According to the definition of a slithy language, the string that is formed by taking the first letter of y and putting it at the beginning of x is also in L. This is because the first letter of y is inserted at the beginning of x. However, the length of this new string, Iyl, is greater than the length of the previous string, Ixl, which contradicts the premise that x and y have distinct lengths. Because of this, each and every slithy language has to have two strings that are exactly the same length.