0
$\begingroup$

I am learning about languages but struggling with operations on them. In my book there are some simple examples but how would I for example describe a language over $\Sigma=\{0,1\}$ such that every word is of length $n$ or greater (with $n \in \mathbb{N}$ and fixed, say $n=5$) AND every word contains at least two $1$'s?

  • 1
    You just did describe it. Are you perhaps wondering how to describe it in terms of a regular expression or a regular grammar?2012-11-17
  • 0
    I would like to know how to describe it using operations. Like $\{00, 11, 01, 10\}^*$ describes the language over $\{0,1\}$ that consists of all even-length strings.2012-11-17
  • 0
    That’s not really using operations: that’s simply listing them. The language of words of length at most $5$ containing at least two $1$’s is a lot bigger; are you sure that you just want to list its members?2012-11-17
  • 1
    It sure is an operation, namely the kleene star operation.2012-11-17
  • 0
    You can do something like $$\bigcup_{\substack{a,d,c,d\in \{0,\ldots, n\}\\ a+b+c+d \le n\\ b+d \ge 1}} \{0\}^a\{1\}^b\{0\}^c\{1\}^d$$2012-11-17
  • 1
    Ah, yes: I didn’t notice the star before; was it perhaps at midline instead of an exponent? Anyway, now I know what you want: you want a regular expression. Unfortunately, that’s going to amount very nearly to listing the words, on account of the length limitation; you won’t get any very significant compression.2012-11-17
  • 0
    @ Brian, yes I'm sorry It was at midline at first...2012-11-17

4 Answers 4