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

6
votes
0answers
110 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
4
votes
0answers
120 views

Applying the Myhill-Nerode Theorem

Consider the language $$L=\{x y^{(n)} z y^{(n)} w: x,z,w \in \Sigma^*, y \in \Sigma, z\text{ does not contain }y, n \geq 0 \}.$$ To show that the language is not regular using the Myhill-Nerode ...
3
votes
0answers
74 views

Is regular following language?

I try to prove that the language $L$ is not regular: $$ L = \{w\in(a+b)^*:\#_a(u)>2009\#_b(u)\ \text{for every nonempty prefix u of word w} \} $$ Note: $\#_a(u)$ means the number of symbols $a$ ...
3
votes
0answers
1k views

Pumping lemma for $a^nb^{2n+1}$

I know how to solve pumping lemma for $a^nb^n:n\geq 0$. But I don't understand how can I solve this example : $a^nb^{2n+1}:n\geq 0$. I tried to solve it but I am not sure that I have solved it ...
2
votes
0answers
30 views

Difference of a regular language and a context-free language

I know that given the context-free language L and the regular language R, the language L \ R is context free. But what about R \ L ? My attempt is as follows: R \ L = R $\cap$ $\overline{L}$ We ...
2
votes
0answers
27 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 ...
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 ...
2
votes
0answers
50 views

Is $L = \{a^n b^m b^m \mid n,m \ge 0 \}$ regular language or not regular language?

Is $L = \{a^n b^m b^m \mid n,m \ge 0 \}$ regular language or not regular language? I think that $L$ is regular because the regular expression a*(bb)* describes ...
2
votes
0answers
29 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 ...
2
votes
0answers
73 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 ...
2
votes
0answers
43 views

show that language is regular

Let $B_n = \{a^k\ |\text{ where } k\text{ is a multiple of } n\}$. Show that for each $n\ge 1$ the $B_n$ language is regular. My proposition of solution: What about it ?
2
votes
0answers
65 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
447 views

Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
1
vote
0answers
15 views

Elementary proof that a particular language is not regular

I want to show that given an alphabet $A = \{ L, R \}$, the language $$ \mathcal{L} = \{ x_{1} \ldots x_{n} \in A^{*} : \# \{ j \leq n : x_{j} = L \} = \# \{ j \leq n : x_{j} = R \} \}$$ cannot be ...
1
vote
0answers
57 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 ...
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
0answers
39 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
0answers
19 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
32 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
0answers
39 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
0answers
29 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 ...
1
vote
0answers
30 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 ...
1
vote
0answers
65 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', ...
1
vote
0answers
30 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
vote
0answers
49 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
0answers
51 views

Why is $a^nb^n|n\geq1$ not regular and $a^nb^n|n\leq {10^{10}}$ regular?

I've heard somewhere that since the latter is bounded, it is regular. Can anyone explain me what a bound actually means? And if the latter is regular, then how would you write the regular expression ...
1
vote
0answers
325 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
1
vote
0answers
75 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
1
vote
0answers
70 views

Nonregular languages that satisfy the pumping lemma at different strengths

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones) The three versions are as ...
1
vote
0answers
98 views

Proving irregularity using Myhill-Nerode theorem

I'm trying to prove that the following language is irregular using the Myhill-Nerode theorem $$ L = \{ w\space\epsilon \{a,b,c\}^* | \#_b(w) > (\#_a(w) + \#_c(w))! \} $$ While it's completely ...
1
vote
0answers
39 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
1
vote
0answers
56 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
1
vote
0answers
46 views

Constructing a Turing decidable machine from DFA

I am a trying to prove that every regular language is decidable. So in order to prove that I am trying to show that I can move from deterministic finite automaton (DFA) to a Turing decidable machine. ...
1
vote
0answers
79 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
1
vote
0answers
50 views

Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
1
vote
0answers
78 views

Proving that language is regular or not regular

Let $L$ be a regular language. Prove that: $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$ $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$ ...
1
vote
0answers
90 views

Isn't the set of all literature a regular language?

Let one piece of literature be one string. Let's define our alphabet to be sufficient to represent all literature (e.g. we may need a page-turn character, etc). So, since the collection of current ...
0
votes
0answers
20 views

First and Follow for the Context Free Grammar

I am trying to understand how to calculate first and follow for given rules Let's say here are two grammars. They are quite unusual so I am not sure if I made any mistakes. ...
0
votes
0answers
58 views

Converting Automata To Regular Expression Using State Removal Method

From the following automaton this solution is given: $$(a\mid b)^*aa(ba)^*a(a\mid b)^*$$ But when I try to convert this automaton into a regular expression I always end up with the wrong ...
0
votes
0answers
24 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
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?
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
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 ...
0
votes
0answers
22 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
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
0answers
152 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} ...
0
votes
0answers
32 views

Proving by using intersection construction that language is regular

L is a regular language and Σ is the alphabet . Proof using intersection construction that L' is a regular language. which languages I should intersect?