In this class we will talk about alphabets A and languages L. An alphabets A is

Question

In this class we will talk about alphabets A and languages L. An alphabets A is any non-empty nite set. We let A* be the set of all nite strings of elements from A. So A* is innite. Languages are sets whose elements come from some A, so they are subsets of A.
Consider the language L = { x | x is a binary string starting with 11 and ending with a 1 followed by an even number of 0’s} = { x | x = 11y10t where y {0,1} and t 2 is even }.

1). Give an example of a subset B of L which is innite and for which L-B is also innite.
2) Give an example of a language K with the same alphabet as L and such that K-L = { 0111, 100, 11, 000, 1010000 }.

3) True or false: Any two languages are equal if and only if they have the same elements

Explanation / Answer

1)

example for B is : { x | x is a binary string starting with 11 and ending with a 1 followed by an even number of 0’s that are muliple of 4}

Now

L contain all the strings which end with even number of 0's only

means length of 0's is a multiple of 2

B contain all the strings which end with even number of 0's that multiple of 4

means lenth of 0's is a multiple of 4

and B is infinite

so...B is subset of L

and L-B is also infinte

2) one simple example of K can be { 0111, 100, 11, 000, 1010000, 110100 }

after doing K-L = { 0111, 100, 11, 000, 1010000 }.//last string is removed

3)True

two languages said to be equal if they have the same elements only

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.