The Gateway to Computer Science Excellence
0 votes

Can anyone explain how S2 is false,I did not understand their logic.

in Theory of Computation by Active (2.5k points)
edited by | 124 views
See here they're talking about equality

if a language  accept epsilon

if we  subtract epsilon from the lang than its not remain the same language anymore than it become totally a different lang right ???
So L+ isn't a different language,I did not understand this.

Hey suppose Σ = {a,b} then we know 

Σ* = { epsilon , a, b, aa , ab, ba ,bb ,........}

Here's definition of Language : A language is a set of string all of which are chosen from some ∑*, where ∑ is a particular alphabet.

So a Language can be anything as  well as : L = { epsilon } is also a valid language.( A language that excepts empty

Now L* will obviously be L* = {epsilon} so , L* - {epsilon} = empty set. So second statement will not be always true. I have no formal answer but I hope this counter example I provided helps


Thanks :)
This example helped thanks a lot :p

1 Answer

+1 vote
Because L* will definitely contain Epsilon in it.

Suppose L = {a,b},

then L* = { epsilon , a , b ,aa, ab, ba, bb, ........}

Therefore L* - {epsilon} = {a, b, aa, ab, ba, bb, ..........}

Thus L* - {epsilon} is not equal to L*
by (225 points)
It's L+ not L*
sorry, the image was not clear. anyway this was my first answer and I don't know if we can delete our answers. Can we delete our answers?
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,737 questions
57,376 answers
105,311 users