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
1answer
18 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
24 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
19 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
24 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
15 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
153 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
23 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
23 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
23 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
25 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
41 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
20 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
25 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
29 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
18 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
17 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
26 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
274 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
23 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
29 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
16 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
29 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
19 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
123 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
20 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 ...
2
votes
1answer
40 views

Is this language context-free or not?

I have a problem to solve, the problem is: Is the language of strings $$L=\{0^x1^y:x\nmid y\}$$ context free? I suspect it isn't, I spent some time trying to make a grammar that could ...
0
votes
1answer
16 views

Proving regular languages

I am given the language L = {a,b}* and a/L = { w ∈ {a,b}* | aw ∈ L }. I am trying to prove that that if L is regular so is a/L. My approach so far is the prove that L is regular (using pumping lemma) ...
1
vote
1answer
28 views

Repeated rules in Chomsky normal form

My question is simple, when you're converting a grammar to CNF, what happens when a rule begins to repeat multiple times? ¿It's good to end with rules like $U_1 \rightarrow SB, U_2 \rightarrow SB, ...
0
votes
1answer
21 views

Prove a language isn't regular using Myhill-Nerode thm.

Let $L$, a language above $\Sigma = \{x,y, (,),+,* \}$. $L$ can be defined recursively as follows: Basis Clause: $x$ and $y$ are in $L$. Inductive Clause: If $\alpha$ and $\beta$ are in $L$, then ...
0
votes
1answer
38 views

Explaining Ultimate Periodicity.

I'm revising for an exam and I've stumbled by Ultimate Periodicity. The exercise is: Prove that $A = \left\{ a^{n^2} \mid n \in \Bbb{N} \right\}$ isn't regular. Can someone explain how we get ...
0
votes
1answer
20 views

Proving that $L^*$ is regular if $L$ is

I know that if $L\in REG$ then you can build an automata that accepts $L^*$, but I was wondering if my approach is also good. I thought about showing that $$L^*=\{\epsilon\} \cup \bigcup_{n\in ...
0
votes
1answer
57 views

Creating a language

I am given a list languages, say $L$, over alphabet $\{a,b\}$. A function $f$ is defined such that $f(i) = L$ for $i ∈ N$. I am trying to a construct a language $D$ which is not in the list (aka. $D ...
1
vote
1answer
37 views

Proving with pumping lemma

I am trying to prove that the follow language is not regular L = {w ∈ {0, 1}∗ | the number of 1s in w is one more than the number of 0s} My approach was to prove that it is regular and prove by ...