# Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

1,600 questions
Filter by
Sorted by
Tagged with
62 views

### Why equality is decidable for regular language but not for $CFL?$

There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. ...
46 views

63 views

### Can a non-deterministic finite automaton die out before reading the entire string?

I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by: However, my problem is: If the ...
64 views

### Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
83 views

### Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma. I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
2k views

### Is it possible to build any regular expression in a computer language with just 3 basic operators?

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
54 views

### Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
120 views

### Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $?$

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
842 views

### Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
88 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 ...
34 views

### Is my regular expression correct for this question?

IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
49 views

### High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
2k views

### Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?

The language given is $L = \{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$. Is this language regular or not? Since there is no pattern, so it should be non-regular? Kindly help!
58 views

### Are the regular expressions equivalent?

Is the following equivalence true? $$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$ I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
85 views

46 views

### If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?

If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular? I think I found a correct proof for this question but my professor says it ...
119 views

45 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$ ...
29 views

### Minimal state DFAs for a regular expression of length $n$

I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
### In what bases is the language $a^n$ regular?
Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular $$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$ I think it's regular ...