in Theory of Computation edited by
322 views
1 vote
1 vote
1] ∅^* = ?

2] ∅^+ = ?

3] ∅ . ∈ = ?

please describe your answers.
in Theory of Computation edited by
322 views

2 Answers

7 votes
7 votes
Best answer

Here the given language is $\phi$ which is empty set {} .

So , L={}=$\phi$

now , we know by definition for any language $L^{0}=\left \{ \epsilon \right \}$

$L^{1}=\left \{  \right \}=\phi$

$L^{2}=L.L=\left \{  \right \}\left \{  \right \}=\left \{  \right \}=\phi$

$L^{3}=L.L.L=\left \{  \right \}\left \{  \right \}\left \{  \right \}=\left \{  \right \}=\phi$

So ,

$\phi^{*}=L^{*}= L^{0}  \cup L^{1} \cup L^{2} \cup L^{3} \cup L^{4} \cup L^{5}\cup………….  $

 $\phi^{*}= \left \{ \epsilon \right \} \cup \left \{  \right \}\cup\left \{  \right \}\cup\left \{  \right \}\cup………...$

$\phi^{*}=\left \{ \epsilon \right \}$ 


$\phi^{+}=L^{1} \cup L^{2} \cup L^{3} \cup L^{4} \cup L^{5}\cup………….  $

 $\phi^{+}$ =$\left \{  \right \}\cup\left \{  \right \}\cup\left \{  \right \}\cup………...$

 $\phi^{+}$=$\left \{  \right \}$


For 3rd  I think the question wrong as $\phi$ is a set and $\epsilon$ is a string . So how can we define an Cartesian product of a set an a string ? Moreover Cartesian product term is wrong for language concatenation as Cartesian product will give us ordered pair not a language.

More details explained in the Link.

edited by

11 Comments

@Deepak Poonia sir for the last one  is my explanation correct ?

0
0
Yes, correct
0
0

@Shaik Masthan thanks sir. Sir I am not able to load equation editor while writting answers . Can you help me in this ?

0
0
Working fine for me... Can you check once again now ?
0
0
Yes sir it is working now .Thanks !!
1
1

@Kabir5454

1. Using the word “Cartesian Product” is Wrong for Language Concatenation.

Cartesian product of two languages is NOT a language, hence, Cartesian product operation is NOT defined over languages, even though they are sets. 

$L_1 . L_2$ is Language Concatenation, Not Cartesian product.

If $L_1 = \{a \}, L_2 = \{b \}$ then $L_1 .L_2 = \{ab \},$ BUT what will be Cartesian product $L_1 \times L_2$?

Cartesian product $L_1 \times L_2 = \{ (a,b) \}$ which is NOT a language. 

Hence, Cartesian product operation is NOT defined over languages, even though they are sets. 

2. The given question is NOT well framed question. The context is missing.

If $\epsilon$ is a string & $\phi$ is a language then $\epsilon.\phi$ is Senseless(undefined).

If $\epsilon$ is a regular expression & $\phi$ is also a regular expression then $\epsilon.\phi$ is a regular expression which is $\phi$.

If $\epsilon$ is a regular expression & $\phi$ is a language then $\epsilon.\phi$ is Senseless(undefined).


By definition of (any) Binary Operation, An Operation $*$ is called a Binary Operation on a Set $S$ iff $\forall a,b \in S, (a*b \in S).$

1
1

@Deepak Poonia thanks sir edited the answer.

1
1

@Deepak Poonia sir 

if they didnt mention anything like Epsilon is null string or Regular expression then by default we take Epsilon as null string 

is it correct??

1
1

Cartesian product of two languages is NOT a language, hence, Cartesian product operation is NOT defined over languages, even though they are sets. 

provided that the cartesian product of two languages is not an empty set.

For example, Consider, a well-defined non-empty set $L_1$ and a well-defined empty set $L_2= \phi$ defined over some non-empty input alphabet.

Then, $L_1 \times L_2 = L_1 \times \phi = \phi$

and $\phi = \{ \}$ is a language and we can make finite state machine for it.   

$L_1 \times L_2 = \phi$ iff $L_1 = \phi$ or $L_2 = \phi$ or both are $\phi$.

1
1

@ankitgupta.1729 Sir it is same as 

  1. Cartesian product is not commutative 

                    but when one of the set is empty set then its commutative 

so should we say Cartesian product is not commutative ( Unless one or both the sets are empty ) ??

0
0
Yes, you can say Cartesian Product is not commutative unless one or both sets are empty or both sets are equal.

Writing only “Cartesian Product is not Commutative” is technically incorrect. It is important to know whatever facts or definition we are using is completely correct or not.

In Calculus, Many people think that $\int_{a}^{b} f$ is defined as $g(b) - g(a)$ where $g$ is a function whose derivative is $f.$

But this definition is wrong.

One of the possible reasons is that $f$ may be integrable without being the derivative of another function.

For example, $f(x) = 0, x \neq 1$ and $f(1) = 1.$ Here, $f$ is integrable but $f$ can’t be a derivative.
1
1
0 votes
0 votes

∅^*:   having power ‘*’ will represent as {ε, s1,s2…..} i.e. ε will always present 

 therefore, for ∅^*: set will be { ε, ∅ } i.e. { ε , {} } => {ε}

 

∅^+:  having power ‘+’ will represent as ∅.∅^*

i.e. ∅.{ε,{}} but anything multiplied with ∅ will always gives ∅ i.e {empty} 

 

∅ is empty set {}

any Set multiply with ∅ will always give ∅ or {}

 

1 comment

Let me know if the answer or anything is wrong.
0
0

Related questions