3
$\begingroup$

Are both Kleene closure(0 or more replication) and positive closure (1 or more replication) special cases of concatenation? Does the number of operands matter here: infinitely countable, vs finite?

Does closure under concatenation imply closure under Kleene and positive closures?

Do the definitions of AFLs and full AFLs from Ullman's Introduction to Automata Theory, Languages and Computation have redundancy?

Define a class of languages to be an abstract family of languages (AFL) if it is a trio and also closed under union, concatenation, and positive closure.

Call a class of languages a full AFL if it is a full trio and closed under union, concatenation, and Kleene closure.

Thanks.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Closure under concatenation does not imply closure under $L \to L^*$ (Kleene closure) and $L \to L^+$ (positive closure): just take the class of finite languages as a counterexample.

$\endgroup$
4
  • $\begingroup$ Thanks. Could you elaborate " the class of finite languages"? What is it? $\endgroup$
    – Tim
    Commented Jun 22, 2020 at 12:22
  • $\begingroup$ A class of languages associates with each finite alphabet $A$ a set of languages on $A^*$. Here I consider, for each alphabet $A$, the set of finite languages on $A^*$. $\endgroup$
    – J.-E. Pin
    Commented Jun 22, 2020 at 12:41
  • $\begingroup$ Is "the class of finite languages" not the power set of $A^*$? Are finite languages those with finite numbers of strings? $\endgroup$
    – Tim
    Commented Jun 22, 2020 at 12:43
  • $\begingroup$ A language is just a subset of $A^*$. Thus yes, a finite language is a finite subset of $A^*$, that is a language containing a finite number of words (or strings, if you prefer). The power set of $A^*$ is larger, since it also contains infinite languages. $\endgroup$
    – J.-E. Pin
    Commented Jun 22, 2020 at 13:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .