# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

7 views

### proving that a regular language can be accepted by a fast finite automata

Let it be L a regular language. Prove that exists a fast finite automata (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which: 1. Q is a finite set of states ...
21 views

### proving that $L_{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_{almost}$ = { w'| exists w∈L so that w' is almost similar to w } a word w' is almost similar to w if they are in the same length, and the ...
16 views

### Prove that the set of palindromes are not regular languages

Let L = {w| w ∈ {a,b,c} * is palindrome} Could someone explain me how to prove that L is not regular, because all answers I've found are done with 2 symbols(a,b), and I'd need to prove it with 3.
17 views

### Regular Expression for a Set of Strings of Even Length

Can the language for the set of even strings be represented by L={ε,aa,ab,ba,bb.....} Isnt Epsilon Odd?
13 views

### If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular?

I need to prove or disprove with contrast example: If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular I have no idea how to begin, hints and spoilers are welcomed
15 views

60 views

### What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$? [closed]

What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$ ?
60 views

### recurrence relation of a language

I am looking at the following: Consider a language $X$ which consists of all bitstrings with no more than 2 consecutive zeros (represented by the above automaton). Next consider a sequence $s_n$ ...
36 views

### Problem with regular expression and set [closed]

Let $S = \{0,1\}$. Given the set: $\{0, 001, 000, 00001, 00000, 0000001,\ldots\}$ What will be the regular expression of the given set?
18 views

### How to find if this language is regular or not

I'm currently having trouble with this one: $$L = \{a^m a^n \mid m, n\text{ is prime}\}$$ I really have no idea. I think it has something to do with Goldbach's conjecture making it impossible to ...
Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows. $$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$ Which of the following ...