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

1
vote
0answers
15 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
17 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
19 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
0answers
16 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
0answers
12 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
23 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 ...
0
votes
2answers
159 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
1answer
12 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
31 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 ...
1
vote
1answer
23 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$ ...
3
votes
1answer
99 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
27 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
3answers
1k views

Regex for strings with no three identical consecutive characters

I wanna ask what the regular expression for the strings having the property in the title should be. For binary string with no three consecutive 0, it's quite a simple regex ...
1
vote
0answers
21 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 ...
4
votes
1answer
386 views

Notation of cross entropy

I have a question regarding a notation that seems to be very usual. For starters, cross entropy is defined by: \begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align} ...
0
votes
1answer
19 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
2answers
12 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
15 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
18 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
17 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
2answers
41 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
2
votes
1answer
19 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
49 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 ...
0
votes
1answer
53 views

How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

How to prove the language of all binary numbers that are prime is not regular using pumping lemma? I have seen Can an infinite set of primes be a regular language or CFG? We have not studied the ...
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
19 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
39 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
15 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
21 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
16 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
41 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
0
votes
1answer
28 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
67 views

Question about formal languages, quotient operator L1/L2.

I come across this problem: Consider the following regular languages: $L1=\{a^*b^*c^*\}$ over the alphabet $A=\{a,b,c\}$ and $L2=\{( a b | b b | a )^*\}$ over the same alphabet as above. Find the ...
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 ...
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 ...
1
vote
1answer
33 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 ...
0
votes
1answer
20 views

proof with using pumping lemma

$L=\{0^n\#0^{2n}\mid n\ge 0\}$ Show that this language is iiregular. And now: Let $p$ will be length of pumping lemma. Given $w=0^p\#0^{2p}=xyz\in L$ such that. Becaues of the fact that $|xy|\le p$ ...
1
vote
1answer
45 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
0
votes
1answer
17 views

Regular expression. Proof.

Let $A = \{a,b,c\} $ be an alphabet. Let $\alpha $ be a regular expression. And: $$ 1) \epsilon \in \alpha \\ 2) a\alpha \subset \alpha \\ 3) b\alpha \subset \alpha $$ Prove, that: $$(a+b)^* \subset ...
0
votes
1answer
29 views

Understanding pumping lemma - length $p$ - in connection with other thread

I create this thread in connection with Is the following language $L$ regular? I would like to show you why I dont understand where I am wrong. I would like to ask question: $p$ - length of pumping ...
2
votes
1answer
33 views

Non regular language that satisfies pumping lemma

Let $$L = \{ ww^rx \mid w,x \in \{a,b \}^+\} $$ where $\{a,b\}^+$ means the set of words over $\{a,b \}$ that has at least length 1, and $w^r$ is the reverse of $w$. I'm trying to prove that this ...
1
vote
0answers
59 views

Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ $M'=(Q', ...
2
votes
0answers
63 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
4
votes
2answers
155 views

Language with error.

Let $L \subset \{0, 1\}^∗$ be regular language. $$L_e = \{ w | w = uxv, x \in \{0, 1\}, u\overline{x}v \in L\}$$, where $\overline{x} = 1 − x$ Prove $L_e$ is regular language. For example: If $10 ...
1
vote
2answers
72 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
1
vote
1answer
21 views

construction for proof of regularity of language

$L$ is regular. $L'=\{vw:v\in L, w\notin L\}$ Show that $L'$ is regular. I ask you for controlling my construction: $M=(Q,\Sigma,\delta, q_0,F)$ for $L$ $M'=(Q,\Sigma,\delta', (q_0, F') $ ...
0
votes
1answer
23 views

$L$ is regular. Show that $Root(L) $ is also regular

Let $Root(L)=\{w \mid \exists {n\in \mathbb{N}} \text{ such that } w^n\in L\}$. How to deal with it ? I tried think about modifications connected with automat for $L$, but it failed. Help me, please.
0
votes
1answer
101 views

show that language $L'$ is regular (given $L$ regular)

Let $L$ be a regular language. Show that $L'=\{x \mid\exists_{y,z} xyz\in L \text{ and }|x|=|y|=|z|\}$ is also regular. Firstly I show my idea. When you accept it I will try to formalize it. Every ...
2
votes
1answer
641 views

Complement of a regular expression?

What is the regex for the complement of $r = b^*(ab + a^* + abb(b^+))^*$ ? I am thinking $(a+b)^*(abb)^+a^* $ since anything that contains $abb$ and is not followed by $b$'s would not be accepted ...