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.

learn more… | top users | synonyms

0
votes
0answers
13 views

Proving by using intersection construction that language is regular

L is a regular language and Σ is the alphabet . Proof using intersection construction that L' is a regular language. which languages I should intersect?
1
vote
1answer
22 views

examples of “interesting” star-free languages

Can you point me to some examples (preferably known ones from the literature, but this is not crucial) of "interesting" / non-trivial star-free languages? I'm trying to get some intuitive sense of ...
-1
votes
2answers
47 views

Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular [closed]

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove ...
2
votes
0answers
31 views

Is $L = \{a^n b^m b^m \mid n,m \ge 0 \}$ regular language or not regular language?

Is $L = \{a^n b^m b^m \mid n,m \ge 0 \}$ regular language or not regular language? I think that $L$ is regular because the regular expression a*(bb)* describes ...
0
votes
0answers
24 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
2
votes
2answers
28 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?
1
vote
1answer
22 views

Creating a regex expression for a regular language

$\{x \in \{0, 1 \} : x = 0^m1^n \hspace{.1cm} \text{for some} \hspace{.1cm} m, n \in N \hspace{.1cm} \text{such that} \hspace{.1cm} m * n \ge 3\}$. I've been stuck on trying to create a regex for ...
-1
votes
1answer
94 views

Math replacing natural language [closed]

Before reading any further. I ask yous to think creatively on this subject. I was in shower and was pondering over A.I. (Strong A.I. both at human level and beyond human level) as I do from time to ...
0
votes
1answer
22 views

proving a implication with regular expressions

I'm trying to prove the following implication to be false: R*(T+S) $\equiv$ R*(TS) $\implies$ T $\equiv$ S. Proof: We have that IF R*(T+S) $\equiv$ R*(TS) THEN T $\equiv$ S Let R, T = ∅ and S = ...
2
votes
2answers
35 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
1
vote
1answer
20 views

Using Myhill Nerode

I'm trying to prove to following language is not regular, using Myhill Nerode's theorem: $L = {a^{n^2}}$ I found this: $a^n$ (has no equivalence classes to) $a^m$ when n ≠ m because $a^na^n$ is ...
1
vote
1answer
21 views

Arden rule proof

I'm studying Arden's Rule for regular languages, but I'm having troubles with the proof. Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation ...
2
votes
0answers
20 views

Question about periodic points in shift spaces

Let $A$ be a finite set endowed with the discrete topology. Then, the pair $(A^{\mathbb{Z}}, \sigma)$ is said to be the full shift over the alphabet $A$ where $A^{\mathbb{Z}}$ is endowed with the ...
1
vote
2answers
27 views

What are some quick things to look for to see if a language is regular or context-free

Without using proofs or pumping lemma, but just by looking at the given language by eye, what are some quick tips and techniques that can be used to see that a language is regular, or that a language ...
1
vote
1answer
16 views

Is Σ* the same as saying L*

I'm getting confused over the two. Are they the same? The complement of a language L is Σ* - L. Is saying L* - L wrong?
0
votes
0answers
18 views

How can one prove that the Thue-Morse sequence is a morphic sequence?

The Thue-Morse sequence is the infinite sequence $\mathbf{a} = (a_n)_{n \geq 0}$ with $a_n = 0$ if the sum of the digits of the binary expansion of $n$ is even and $a_n = 1$ otherwise. Consider the ...
4
votes
3answers
174 views

Number of states in a finite automaton

How many states are required by a deterministic finite automaton to store $m$ words each of length $n$? I came across $2^{mn}$ as the solution but there was no explanation.
1
vote
1answer
8 views

Regular and not regular based on the value of n

If $L = \{a^nb^n, n \leq 100\}$ is regular, is $L_2 = \{a^nb^n, n > 100\}$ also regular? $L$ is regular because we can draw an FA(finite automata) for it. It's not possible to draw an FA for ...
0
votes
2answers
28 views

Why is the below language regular?

If I have a language $$L=\left\{wxwy : w,x,y \in \{a,b\}^+ \right\}$$ I am not getting how come we are able to write regular expression for this of the form $$a(a+b)^+ a(a+b) ^+ + b(a+b)^+ b(a+b) ...
0
votes
0answers
26 views

Periodic Shifts of finite type

I am learning about periodic shifts and want to look at finite types of periodic shifts. So I have this theorem: A shift space $X$ is an $M$-step shift of finite type iff whenever $uv, \; vw\; \in ...
1
vote
0answers
25 views

Why does a certain turing machine only accept regular languages?

why does a single tape turing machine, which can not write on the part of its tape containing the input, only accept regular languages? I am asking this because this question is being opposed to me ...
1
vote
1answer
24 views

Product of two DFA.

Let $ A, B \subset \{ a, b\}^* $ and $A, B$ be regular. Lets define: $ A \circ B = \{ w \in A | \exists y \in B , \#_aw = \#_ay \}$ where,for example: for $ w = aaabaaba$ $\#_aw = 6, \#_bw = 2 $ ...
1
vote
1answer
11 views

Closure under splitting?

Say there is a regular language $L\subseteq \lbrace 0,1\rbrace^\ast$ Would the language $L_1 =\lbrace w\in\lbrace 0,1\rbrace^\ast | w0\in L\rbrace $ also be regular? (i.e. $L = L_1\circ\lbrace ...
0
votes
2answers
30 views

How to draw a DFA for complement of a regular language using a regular expression?

How can I draw an FA for the complement of the language $L(r)$? $L(r) = a^* (aba^*)^* b^* a^*$ I can draw an FA for $L(r)$ and convert to DFA and then take the complement, however it seems very long ...
1
vote
2answers
44 views

Proving that $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not a regular language

I'm having trouble using the pumping lemma to prove this language $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not regular. Assume $L$ is regular. Thus there is a DFA $M$ for it. Choose $m$ as the ...
2
votes
1answer
30 views

Concatenation of Finite Languages and Regular Languages

I know that the following statements regarding Concatenation are false. However, I'm having difficulty explaining why they are false with simple counter-examples. I'm able to find simple ...
-1
votes
2answers
26 views

Is the intersection of a finite language and an infinite language always a regular language?

Is the intersection of a finite language $L_1$ and an infinite language $L_2$ always a regular language? I've tried a few examples and the result always seems regular. $\{\} \cap a^nb^n = \{\}$ ...
1
vote
0answers
17 views

If $L$ is context-free, then $L$ is regular

Let $L \subset \{a\}^*$ and assume that $L$ is context-free. Prove that $L$ is regular. Please hint me.
1
vote
0answers
18 views

Showing that language $L^{'}$ is regular given $L$ is regular [duplicate]

Say $L \subseteq \{a,b\}^*$ is a regular language with words whose length is divisible by 3. Each word $w \in L$ has the form $w=xyz$ with $|x|=|y|=|z|$, where $y$ is then called the middle third of ...
0
votes
1answer
33 views

Pumping Lemma for Regular Language (Is my answer correct)?

I've been working on understanding the Pumping Lemma for 2 days now and I feel like I may have finally got somewhere. I was hoping to show you guys a question and my working out and if you think i'm ...
0
votes
1answer
22 views

On the existence of a non-regular language $L$ such that $L^2\in \text{Reg}$?

Is there a non-regular language $L$ such that the language $L^2$ is regular? Nothing comes to my mind. What's your proposition ?
0
votes
1answer
19 views

Check if language and complement is context free

$L=\{u\$w^R|u,w\in \{a,b\}^+ \text{$w$ is prefix and suffix of $u$ }\}$ Check if language $L$ and $L^C$ is context free. L $a^*b^*\$a^*b^*\cap L = \{a^ib^j\$a^ib^j|i, j\ge 0\}\notin CFG$ So, $L$ is ...
1
vote
0answers
26 views

How many states (minimally) for an automaton recognizing the set of words without palindromic subwords on a $k$-letter alphabet?

Let $\Sigma_k = \{0,1,...,k\}$ and let $NPA_{k}$ be the set of words that do not contain a palindrom (of length $\ge 2$) as a subword. How many states (minimally) must have an automaton that ...
1
vote
1answer
18 views

Check if $L$ is regular then $L'$ is regular (and and vice versa)

let's define $w\leftrightarrow v$. It does mean that we may "create" $w$ using word $v$ in following way: every single letter $x\in \Sigma$ in word $v$ may be replaced by $xx$, and every double ...
1
vote
0answers
32 views

Are all finite languages regular?

I've been thinking about this for a while and still cannot come up with a way to show that all finite languages are regular. I know that all finite languages consist of finite number of strings that ...
0
votes
0answers
10 views

Is my LL(1) parse table correct?

I have the following Grammar: ...
1
vote
1answer
27 views

Prove the following language is not regular using pumping lemma.

Prove the following language is not regular using the pummping lemma $L = \{a^{n!} \mid n\geq0, n\in\ \mathbb{N} \}$. What I have done so far is: Assume $L$ is regular. So, there is a $DFA$ for $L$ ...
0
votes
2answers
304 views

Why are every finite language decidable?

I don't understand why every finite language is decidable. For example, if I have an infinite set of strings L over an alphabet E, why is there a Turing Machine M that decides L? I understand the ...
1
vote
0answers
23 views

Check if language $L^2$ is regular

$L=\{w|w\in\{0,1\}^*\wedge \#_1(w)=\#_2(w)\}$, where $\#_a(w)$ denotes number of symbol $a$ in word $w$. Check if $L^2$ is regular. So idea is: $L^2 \cap 0^*1^*0^*=\{0^n1^{2n}0^n|n\ge 0 \}\notin ...
0
votes
1answer
24 views

Constructing regular expressions for languages

I'm new to regular expressions and I'm currently working on some exercises to get familiar in constructing regular expressions for languages. I have the following languages, for which I already tried ...
0
votes
1answer
30 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
0
votes
2answers
19 views

Languages and their Regular Expressions - Automata

I am working on some Automata practice problems. I am working a 2 part question. Here it is: Let $\Sigma = \{a,b\}$ be an alphabet. Let $L = \left\{w \in \Sigma^* \mid n_a(w) \le 4\right\}$ ...
1
vote
1answer
32 views

Pumping Lemma proof and the union/intersection of regular and non-regular languages

I am still learning the pumping lemma. I have a problem for which I used it. I used it on the first part (a) but I am unsure if it is correct. Parts b-d, I am not sure how to do it. I created a dfa ...
0
votes
1answer
21 views

Using the Pumping Lemma To Prove A Language Is Not Regular

I am taking a Automata class and we just went over the Pumping Lemma. Initially, it did not make sense. I am still not fully comfortable but I have started trying to use it to prove that a language is ...
0
votes
1answer
24 views

Context Free Grammer (CFG) for a language

Consider the language above $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y : x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need define a CFG for this language. I've tried couple of ...
2
votes
1answer
20 views

Prove that regular languages are closed under operation

Operation $random$ is defined on two words with equal length in the following way: $\forall w_1,w_2 \in \Sigma^* s.t. |w_1|=|w_2|=n, w_1=a_1a_2...a_n, w_2=b_1b_2...b_n:$ $Random(w_1,w_2) = ...
0
votes
1answer
58 views

Context-free languages closure property

Trying to rove that the set of all context-free languages over a language Σ is closed under TRIPLE where TRIPLE (L1, L2, L3) = L1L2L3. Pretty much, TRIPLE, applied to three languages yield the ...
3
votes
1answer
124 views

Pumping lemma and $L \subset \{a\}^*$

Let $L \subset \{a\}^*$ and $L$ satisfies pump lemma. Prove that $L$ is regular. Please help me. My an attempt: Definition. A language $L$ of $A^∗$ is recognized by a monoid $M$ if there is a ...
0
votes
1answer
25 views

What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?

Let $L = L((00 + 1)^∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$? In this context "$+$" means "$\cup$". So the language $L$ is all the ...
1
vote
0answers
22 views

$L$ is regular. Prove that $D(L)$ is also regular

I ask you for look at my solution: $L$ is regular. Prove that $D(L)=\{w|ww^R\in L, w\in\Sigma^*\}$ is also regular. Idea I go through states from two places (two fingers). When fingers meet in the ...