Skip to main content
Computer Science

Return to Question

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

 

$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,

 

where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.

 

For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

 

$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,

 

where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.

 

For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,

where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.

For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

formatting, title, more concise problem statement.
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Prove that if $L$ is regular, then soREG is $\mathcal{B}closed against removing all but lexicographicaly largest words (Lper length)$

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,

where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.

For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

$\mathcal{B}(L) = \{ x \in L : x \text{ is the lexicographically largest among all strings of length } |x| \text{ in } L \}$. For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$. Any Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Prove that if $L$ is regular, then so is $\mathcal{B}(L)$

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

$\mathcal{B}(L) = \{ x \in L : x \text{ is the lexicographically largest among all strings of length } |x| \text{ in } L \}$. For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$. Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Prove that REG is closed against removing all but lexicographicaly largest words (per length)

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,

where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.

For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Tweeted twitter.com/#!/StackCompSci/status/516432266059198464
Source Link
David Smith
David Smith
  • 493
  • 2
  • 8

Prove that if $L$ is regular, then so is $\mathcal{B}(L)$

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

$\mathcal{B}(L) = \{ x \in L : x \text{ is the lexicographically largest among all strings of length } |x| \text{ in } L \}$. For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$. Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.