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
36 views

Prove about $NFA$ and pumping lemma

The question: Let it be $L$ a regular language. few definitions: $p(L)$-the minimum natural number so that $L$ fulfills the pumping lemma. $n(L)$- minimal NFA that accepts $L$. $m(L)$- $Rank(L)$, the ...
1
vote
1answer
22 views

Concatenation of unknown language

$$If \space L_1L_2\space is \space regular, then \space L_2L_1 \space is\space regular$$ Is this statement correct? I can't seem to find any counter example. Besides, what is a good way of tackling ...
0
votes
2answers
17 views

Regularity of a language

$$ L = \{w \mid w \text{ does not contain } 000\} $$ $$ L_2 = \{w \mid xwy \in L \text{ for some } x,y \in (0+1)^*\} $$ Is $L_2$ regular? I am thinking regular language is closed under concatenation, ...
0
votes
1answer
27 views

Regular Pumping Lemma

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$ Determine if each language is regular or ...
2
votes
0answers
28 views

Regular Expressions with Repetition

I'm learning about regular expressions and how they represent regular languages of an alphabet. Conceptually, I'm having trouble imagining what a regular expression would look like, representing a ...
0
votes
1answer
25 views

Prove that relates to pumping lemma that I am not sure about

So, I will define like in my last post (for a regular language $L$): We will define $p(L)$ to be the minimal natural number so that a language $L$ fulfill the pumping lemma. We will also define $n(L)...
0
votes
0answers
29 views

How to prove that a simple NFA is minimal, without any algorithm?

First, I will present the question I was doing: We will define $p(L)$ to be the minimal natural number so that a language L fulfill the pumping lemma. We will also define $n(L)$ to be the minimal NFA ...
0
votes
1answer
19 views

Do the initial segments of the strings of a regular language form a regular language?

Let's say you have a set of strings $R$. A string $s$ is part of my language $S$ iff there is a string $r \in R$ such that $s$ is an initial segment of $r$ (you can get $s$ by removing characters from ...
0
votes
0answers
27 views

Is the resulting language regular?

If $L$ is a regular language then is $L'=\{w \mid wx \in L \text{ for some string }x\}$ regular? First step is understand $L'$. So it is a subset of $L$ that contains strings with a certain prefix?
1
vote
1answer
33 views

Cocke-Younger-Kasami (CYK) Proving a word is in a language

Using CYK algorithm I need to figure out whether the word abbabb is a word of the language of the following grammar. I think I have completed the problem correctly but I'm not sure, I'm hoping ...
1
vote
1answer
156 views

What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
0
votes
1answer
25 views

Identify the class of language?

Given a set $$S=\{x∣ \text{there is an x-block of 5's in the decimal expansion of π}\}$$ (Note: x-block is a maximal block of x successive 5's). Identify class of language? Somewhere it ...
0
votes
1answer
41 views

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: $010010\in \...
1
vote
0answers
60 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be invalid....
0
votes
1answer
40 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr L=\{\overbrace{\epsilon}^{0^2},\...
1
vote
1answer
22 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
0
votes
1answer
127 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
2
votes
1answer
36 views

Writing a regular expertion for the language $L=\{0^n1^m \mid n\equiv m\pmod 2\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
0
votes
1answer
12 views

Language of all the binary words that not contains continuum of more then $3$ zeros

I need to write a regular expertion for the language of all the binary words that not contains continuum of more then $3$ zeros, for example $0011110100\in L,\,\,\,\,\,\,\,\,\,11000001100\notin L $ ...
0
votes
1answer
26 views

Language of all the binary words that contain $010$ at least twise

I need to write a regular expertion for the language of all the binary words that contain $010$ at leasr twise, note that $101010$ should be accept too because $1\color{blue} {010}10$ and $101\color{...
2
votes
0answers
20 views

General question about pumping lemma statement for regular languages

According to the formal statement of the lemma here: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages It is written at (3) that for all $i≥0, xy^iz∈L$. Until this ...
0
votes
2answers
50 views

Using the Pumping Lemma to show that the language of all strings of even length having no $0s$ in their second half is not regular

I'm struggling with finding a starting string $s$ to prove using the Pumping Lemma that language $$L = \{w \mid w\text{ has even length and the second half of $w$ does not contain any $0$s}\}$$ is ...
1
vote
2answers
40 views

Checking whether a Language is Regular

I have the following question My approach in solving this problem would be. For a language to be regular we should be able to create a Finite Automata that could accept it.In the above example n ...
4
votes
1answer
56 views

Finding a general formula for a regular expression

I need to find the general formula for the regular expression $(S+T)^n$ where $S$ and $T$ are arbitrary regular expressions over a one-letter alphabet and $n$ is an arbitrary natural The general ...
1
vote
1answer
71 views

Prove that a language is not regular

I want to prove that $L$ is not regular: $$L = \{ww^Rv \mid |w|\ge1 , |v|\ge 0\},$$ where the alphabet contains at least two symbols. Can someone prove it? I prefer to use "Pumping Lemma for Regular ...
0
votes
1answer
30 views

Wrong prove for $L=\{a^m:m\geq 0,\; m \mod 3\neq 0\}$ isn't regular, but why?

First, let me just say that this language is regular, and I understand why. But before I understood that, I tried proving that L isn't regular with pumping lemma. I just can't figure what is wrong ...
1
vote
2answers
74 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 ...
1
vote
1answer
45 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
45 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
59 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 length,...
0
votes
0answers
26 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
42 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
38 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 ...
1
vote
1answer
30 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
225 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
35 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$ $\sf(TSS)^...
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
55 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
51 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
23 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
35 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
75 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
27 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 ...