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

### 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}$ ...
• 72.6k
5k views

### Algorithms computing if a number is a multiple of 3

When doing mental calculus one can do: Given an integer k, sum all the digits (in base 10), and if the result is a multiple of 3, then k is a multiple of 3. Do you know of any algorithm working ...
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
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
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
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 ...
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
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
1 vote
569 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 ...
558 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
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
### 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$ ...