13 questions linked to/from Regular languages that seem irregular
2k views

### Automaton for telling whether a binary number is a multiple of 3

I am designing an automaton which determines whether a binary number is divisible by 3: $$\{x \in \{0, 1\}^* \mid \text{x represents a multiple of three in binary} \}$$ 0 1 0F 0 1 1 2 0 2 1 2 ...
562 views

### Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states

Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
• 235
165 views

### How to check $L$ is regular or not [duplicate]

If $L=\{w \in \Sigma^*\mid w=uv,\text{ number of occurnce a's in$u$equal to number of occurrence b's in$v$}\}.$ I think $L=\Sigma^*$ because for any string in $\Sigma^*$, we can split it to $uv$ ...
1 vote
571 views

### Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

I'm doing a problem where I need to find the equivalence classes of the language below: Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x ...
462 views

### Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?

I need to prove or disprove if these two languages are same. So I assume that these lanaguages are same because I think that every word from $\{a,b\}^*$ could be concatenated from two words $x$ and $y$...
• 155
15k views

### Regular expression for strings that begin with 0 and contain an equal number of 01 and 10 substrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
• 147
163 views

### DFA for the language L = { $\omega = xy \in (a,b)^*\mid |x|_a = |y|_b$ } [closed]

I need to find a DFA for this language: L = { $\omega = xy \in (a,b)^*\mid |x|_a = |y|_b$ }
• 17
114 views

### Finite strings and relationships between words [closed]

I have a finite alphabet Σ and Σ* refers to the set of all finite strings over Σ. 1) Given x, y ∈ Σ* we say that x is a prefix of y if ∃z ∈ Σ* y = xz. If x is a prefix of y and y is a prefix of x ...
421 views

### Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? There is a book here that claims $L$ is not CF (without any elaboration), ...
• 141
4k views

### Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
• 271
533 views

### Is this language regular or not?

$L_1=\{a^ku \mid u \in \{a,b\}^*$ and $u$ contains at least $k$ a's, for $k\geq 1\}$. If it is regular, I haven't found its regular expression or any closure property to prove it. If not, it seems ...
• 245
### How can it be decidable whether $\pi$ has some sequence of digits?
We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ ...