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
28 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
19 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
16 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
38 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
9 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
18 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
15 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
35 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
27 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
66 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
19 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
30 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
19 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$ ...
2
votes
2answers
30 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 ...
0
votes
1answer
33 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 ...
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
16 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
28 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
32 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
47 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
60 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
152 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
74 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
609 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 ...
1
vote
1answer
37 views

Regular language. Proof

Let $L$ be regular language over $\{0,1\}$. Prove that $L'$ is also regular: $$L' = \{ w | w \in L \mbox{ and among words of length |w|, w is the least in lexicographic order.} \}$$ To explain, for ...
0
votes
0answers
42 views

Is the following language $L$ regular?

$L=\{ww^Rv\mid v,w\in \{a,b\}^+\}$ Is $L$ regular ? Edit Is it ok? Let $p$ will be length of pumping lemma. Then, $a^pb(a^pb)^Rv\in L$. When $a^p(a^pb)^Rv = xyz$ $p\ge |y|\ge 1 $ So ...
2
votes
0answers
23 views

Is it true that if $Cycle(L)=\{uv:vu\in L\}$ is regular then $L$ is regular [closed]

Is it true that if $Cycle(L)=\{uv:vu\in L\}$ is regular then $L$ is regular ? Any clues ?
1
vote
1answer
25 views

Difference between regular and not regular languages

I don't understand the difference, in classes I've seen the pumping lemma for regular languages and I know how to apply it to demonstrate whether a language is regular or not, but I feel that I don't ...
0
votes
0answers
20 views

construct automat for language $Cycle(L)$

We have automat $A$ for language $L$. Construct automat for $Cycle(L)$ where $Cycle(L)=\{uv:vu\in L\}$. I have a problem with this exercise. Help me, please. Edit $A = (Q_A, \Sigma, \delta, q_0, ...
1
vote
1answer
71 views

Clarification of the statement of the Pumping Lemma

In class we were told that Pumping Lemma states: "Let A be a regular language over $\Sigma$. Then there exists k such that for any words $x,y,z\in\Sigma^{*}$, such that $w=xyz\in A$ and $\lvert ...
4
votes
1answer
379 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
14 views

operations which are closest under regularity - other seeing

We have: $L_1, L_2, $ regular and $L_3$ irreguar. Now: $L_1\cap L_2$ is regular. $L_1\cap L_4 = L_3$ Can I say that $L_4$ is irregular ? The same question about $\cdot, \cup$
0
votes
1answer
39 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
1
vote
1answer
22 views

How to show that a language is regular?

Let $L$ be a regular language over $\Sigma$. Show that: $$\left\{ x_1x_2 \dotsm x_k \mid x_1,x_2,\ldots , x_k \in \Sigma, \exists y_1, y_2, \ldots, y_k \in \Sigma: x_1y_1\dotsm x_ky_k \in L ...
1
vote
1answer
43 views

Prove that if $L$ is regular then $f(L)$ is regular

Prove that if $L$ is regular then $f(L)$ is regular. $$f(L)=\{w: \text{every prefix of $w$ of odd length $\in$ L } \}$$ So my attemption is: Let $M= (Q, \Sigma, \delta, q_0,F) $ will be DFA ...
0
votes
0answers
19 views

How to prove that Pumping lemma can't be used to prove regular languages.

I need a prove that pumping lemma can't be used to prove regular language. Pumping lemma is only used for proving non-regular language, but I need to show that how it can't be used to prove regular ...
0
votes
0answers
11 views

regularity of language $D(L)$, $L$ is regular

Show that $D(L)$ is regular, $L$ is regular. $D(L) = \{w|w\in \Sigma^* \wedge ww^R\in L\}$ Let assume that M has only one state accepting. Therefore, $M'$ has only one state start. ($M'$ recognizes ...
1
vote
1answer
68 views

proving by construction that language is regular

I had this exercise saying the following: $$ L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\} $$ I need to prove that $L$ is regular by defining an ...
-1
votes
2answers
30 views

How to Solve Complex Non-Regular Language? [closed]

$L_5={\{ c^n a^m b^p,n+m=p,p≥6}\}$ where $∑=(a,b,c)$ I need little help, I was practicing Pumping lemma, and I encountered this language, I saw these conditions and I got totally confused, what to do ...
2
votes
1answer
41 views

Prove that this language is not regular

I need to prove that the language $$L = \{a^nb^mc^k|n+k\neq3m\}$$ is not regular. Any ideas how I can do that?
1
vote
0answers
24 views

prove that language is regular (other language is regular)

Let $L$ is regular. Prove that $L'$ is regular. $ L'=\{uv: u\cdot rev(v)\in L\}$ $rev(v)=v^{-1}$ Idea: $L^{-1}$ is regular and recognized by $R$, and $L$ by $M$. Let's assume that $M$ is NFA such ...
-1
votes
1answer
35 views

Isomporphism two languages.

Let $A$ be an alphabet. Let $X,L \subset A^*$ $L$ is regular. Let $$X^{-1}L := \{ w \in A^* \mid \exists x \in X\ \ xw \in L \} $$ $$LX^{-1} := \{ w \in A^* \mid \exists x \in X\ \ wx \in L \} $$ ...
0
votes
1answer
43 views

find automata that accepts following language

Find automata, that accepts following language: $L\subseteq\{0,1\}^* $ $$L=\{w|w\ \text{dosen't contatain four 1's in 7 consecutive symbols}\} $$ My only proposition is: It is only fragment, but it ...
1
vote
0answers
42 views

Prove that language is regular given other regular language

Let $L\subseteq A^*$ be regular. Prove that $L'$ is regular where $L' = \{vw \mid \exists u\in A^*\ vuw \in L\wedge |u|=|w|+|v|\}$ Help me please. It is very hard for me, I don't know how to start. ...
1
vote
1answer
32 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
3
votes
1answer
35 views

Regular languages- homomorphism.

Let $h: \{ a,b,c,d \}^* \rightarrow \{a,b\}^* $ be a homomorphism such, that $h(a) = aa, h(b) = ab, h(c) = ba, h(d) = b $ . Determine: $h^{-1}((bab)^*ba^*b).$ I have trying do it by 4 hours. I don't ...