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
2answers
64 views

How to prove that $L=${$a^p$: p is prime} isn't regular?

I tried using pumping lemma or finding infinite equivalence classes, but I didn't succeed. It's clear to me that there is no automata that accepts this language, but I just can't formally prove that ...
0
votes
1answer
42 views

Which of these languages are regular?

Consider the following subsets of $\{ a, b, \$ \} ^*$: $A = \{ xy \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$ and $B = \{ x \$ y \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$. Which of the ...
1
vote
1answer
29 views

proving that if a FFA accepts L=> L is a regular language

Ok, so after wasted time for nothing on this question that I asked yesterday: proving that a regular language can be accepted by a fast finite automaton Now comes the more interesting prove: ...
0
votes
1answer
38 views

proving that a regular language can be accepted by a fast finite automaton

Let it be L a regular language. Prove that exists a fast finite automaton (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 ...
4
votes
2answers
56 views

proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same ...
0
votes
0answers
25 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.
0
votes
0answers
41 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?
0
votes
1answer
16 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
0
votes
1answer
36 views

DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 ...
0
votes
1answer
26 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
0
votes
1answer
15 views

Proof of L being a regular languaje

I have the following language $$L = \{w\in\{a,\;b\}^* : a^nv,\; n\geq 1 \wedge |v|_a \geq n\}$$ Formed by characters "$a$" and "$b$" where the word $v$ has more "$a$" characters than $a^n$. I have ...
1
vote
1answer
208 views

Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let L be regular language, and let half(L) be: $half(L) = \{u | uv \in L\ s.t. |u|=|v|\}$ Prove ...
-1
votes
1answer
34 views

Regular expression language that describes a graph?

Does anyone know of a regular expression language that can be used to describe a chart with time on the x-axis and price on the y-axis? I would use this language to match regular expressions against ...
0
votes
1answer
20 views

Regular Expression definitions, as a rule, what is always true?

If I have two regular expressions $\sf S$ and $\sf T$, what is always true of these? options: Both $\sf(SS \mid T)^\ast$ and $\sf(TSS)^\ast$ are subsets of $\sf(TSS\mid STS\mid SST)^\ast$ ...
1
vote
2answers
38 views

String in an kleene star alphabet

Let Σ = {a, b}. How many strings of length 10 are in the language (bb + aab)*? If this a matter of writing them out or is there a formula to it?
0
votes
0answers
47 views

Prove that $L = \{0^n1^m \mid n ≥ 10, m ≤ 50\}$ is regular and that any subset of it is regular

Question: Let L = {0n1m, n ≥ 10 m ≤ 50}. Prove that this is a regular language and that any subset of it is also regular. Answer or approach: 0 is regular, 1 is regular since any symbol in ∑ is ...
1
vote
2answers
48 views

Prove that $\{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$ is not regular?

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language $$A = \{w \mid \text{ w has even length ...
0
votes
1answer
34 views

Understanding the proof that uses Pumping Lemma that the language $C =\{w \mid w$ has an equal number of $0$'s and $1$'s$\}$ is not regular

I have just started reading about the Pumping Lemma, and I have some difficulties understanding the proofs of non-regularity of languages. For example, in the book I am reading there's a proof for ...
0
votes
1answer
18 views

Algorithm for Regular Language

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses ...
0
votes
2answers
21 views

Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1=\{a^mb^mca^nb^m∣m,n≥0\}$ $L_2=\{a^ib^jc^k∣i,j,k≥0\}$ Then $L$ is Not recursive Regular Context free but not regular ...
1
vote
2answers
33 views

Converting NFA to DFA (exponential).

I understand how to convert from an NFA to a DFA, and the if there are $n$ states in a NFA there will be $2^n$ states in the DFA (without minimizing). Would someone mind explaining the intuition ...
1
vote
1answer
37 views

Prove the infinite union is not regular

Prove $\bigcup _{i=1}^\infty A_i$ is not regular. We know $A_i$ is regular, but how can prove the infinite union is not regular. I think a counter example would work, but I can't think of any. ...
2
votes
1answer
71 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
1
vote
1answer
26 views

Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a ...
1
vote
0answers
27 views

Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
1
vote
1answer
50 views

Pumping Lemma for $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$

Let $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$ I want to prove that this is not a regular language, but I am having trouble finding a string I can pump resulting in the string not being in the ...
1
vote
1answer
734 views

Minimum Pumping Length

What is the minimum pumping length of (01)* The solutions says 1, but can someone explain why that is? I understand this language accepts the empty string, but the minimum pumping length cannot be 0. ...
1
vote
3answers
57 views

Closure property of regular language

I am trying to prove the closure property of regular language with a function $f(w)$ over alphabet $\Sigma$ for any string $w \in \Sigma^*$. $f(w) =$ string obtained by taking symbols of $w$ at even ...
0
votes
1answer
28 views

Context free grammar for these langauges?

I've been working on trying to generate context free grammars for different problems and currently I'm working on these but after trying over and over, I can't come up with ones for these: 1) the ...
0
votes
0answers
21 views

Closure property of regular languages

I am trying to understand the closure property of regular languages. I am defining two functions func1(w) and func2(w) over alphabet Σ for any string w ∈ Σ∗. func1(w) gets the string of symbols of w ...
0
votes
0answers
31 views

What does it mean “the transition function of FA M is derivable in CFG G”?

I don't understand this question. Let $M$ be a finite automaton. If every production of G is accepted by M and the transition function of $m$ is derivable in G, then $L(G)$ = $L(M) ?$ What does ...
0
votes
2answers
30 views

Is the concatenation of two arbitrary alphabets is considered an alphabet?

Is the concatenation of two arbitrary alphabets is considered an alphabet ? Also Is the set of all Java reserved words is considered an alphabet ? I am inclined to say yes. We could take a string and ...
0
votes
2answers
232 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
0
votes
1answer
39 views

Why do non regular languages have infinitely many equivalence classes?

Let's say I have a language L = {a^nb^m|n != m}, The Myhill-Nerode relation $\equiv_L$ of $L$ is a relation on $\Sigma^*$. It is for words $x,y \in \Sigma^*$ defined by $$ x \equiv_L y \iff ...
1
vote
3answers
44 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
0
votes
0answers
44 views

Topology on a free monoid using regular languages.

A free monoid together with arbitrary unions of regular language subsets forms a topological free monoid. Every free monoid homomorphism is continuous with respect to the topology described in 1. ...
0
votes
0answers
28 views

Using Pumping Lemma to show a language is not regular

Let $$L=\left\{0^n 1^{2n} \mid n > 1\right\}.$$ Show that $L$ is not regular. Attempt: If the language is regular, it must satisfy the Pumping lemma. $P$ will be our pumping length and our string ...
0
votes
2answers
46 views

Prove the intersection of regular languages is regular.

A, B are regular languages. Complement of a regular language is regular Union is regular Prove the intersection is regular. Using these definitions the proof in my book is: $\overline A$ is ...
2
votes
3answers
101 views

Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...
0
votes
1answer
41 views

Prove if a language is infinite

Given M = (Q,Σ,δ,q0,F) a DFA with n states. Prove: The languge T(M) is infinite iff contains a string with lenght t, where n ≤ t < 2n. Ok, it's intuitive for me, I can understand to get a string ...
0
votes
1answer
24 views

Find languages L1 and L2, neither of which contains the other, such that (L1* ∪ L2*) = (L1 ∪ L2)*. [closed]

I'm trying solve this question in several ways, but only textbook has not helped me alot.
1
vote
1answer
37 views

Is $L_1$ context free language?

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L ...
0
votes
0answers
150 views

Construct DFA from context-free grammar

What is simplest and shortest way to build minimal DFA from context-free grammar (equivalent to regular grammar)? For example, the grammar: A ::= aB B ::= {b} ...
3
votes
1answer
36 views

Is C* regular if C is a language with strings of prime length?

Let $C = \{a^p \ | \ p \ \text{is prime}\}$ be a language. I was able to show that $C$ is not regular using the pumping lemma. However, I am having some trouble showing that $C^*$ is regular. ...
-1
votes
2answers
51 views

Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,…$ over the same alphabet?

Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,...$ over the same alphabet ? (a) can $L$ be regular ? (b) Is $L$ always regular ? I want to make sure ...
1
vote
3answers
39 views

If $L_1$ and $L_2$ are regular then $L_1 \cup\;L_2\; = L$ is regular. Is the converse true?

The following is an answer I found to the question. For instance, $\sum^*$ is a regular language; but it can be decomposed into two languages $L_1= \{0^i1^i,\;i\ge0\}$ and $L_2 = ...
0
votes
3answers
65 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^*)$ ?
1
vote
1answer
62 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$ ...
0
votes
2answers
42 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?
1
vote
1answer
20 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 ...