# Understanding the language

Could you please help me understand the following Language

$$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$$ what does $$a_i = a_{i+1}$$ mean? Could you please give me an example of word in $$L$$?

• It means exercise 3 b, I should have removed it – Michael Maier Mar 7 at 15:25
• I should have removed it Don't muse, do: edit your question. – greybeard Mar 7 at 17:06
• (Dubious: $0000$, useful: $0010$, not $0101$: argue why.) – greybeard Mar 7 at 17:09

## 2 Answers

The expression "$$a_i = a_{i+1}$$" means "$$a_i$$ and $$a_{i+1}$$ are equal".

Presumably $$a_i$$ is a symbol, that is, $$a_i \in \{0,1\}$$. Therefore the condition states that $$a$$ contains at least four symbols, and there are two adjacent symbols which are equal, that is $$a$$ contains either $$00$$ or $$11$$ as a substring. Stated differently, $$a$$ contains at least four symbols and it doesn't consist of alternating zeroes and ones (i.e. you are not allowing 0101, 01010, ... or 1010, 10101, ...).

• Thanks for your answer, if I understand it correctly, is for example 010110 a valid word? – Michael Maier Mar 7 at 15:34
• Yes, that's a word in the language. – Yuval Filmus Mar 7 at 15:36

Let's break it down

$$\{\; a \mid a ∈ \{0, 1\}^∗$$ $$\quad$$ a language of words over the alphabet $$\{0,1\}$$

$$|a| = k ≥ 4$$ $$\quad$$ with length $$k$$ at least $$4$$

$$a = a_1a_2...a_{k−1}a_k$$ $$\quad$$ lets call the symbols of $$a$$ with indices $$a_1$$ to $$a_k$$ $$\quad$$

(this is a little implicit here, but OK)

$$\exists i \in N$$, $$1 ≤ i < k$$ $$\quad$$ there exists a natural number $$i$$, a position in the string $$a$$,

$$a_i = a_{i+1} \; \}$$ $$\quad$$ such that the two consecutive letters $$a_i$$ and $$a_{i+1}$$ are equal.

• Thanks for your answer, could you please give an example of such a word? – Michael Maier Mar 7 at 15:27
• Please have a look at the answer by @Yuval. He is quite clear in that part, so I do not feel I need to repeat it. (By accident we answered within 8 seconds or so.) – Hendrik Jan Mar 7 at 15:29