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
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
73 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
784 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
59 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
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
2answers
31 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
305 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
40 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
47 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
48 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
29 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
52 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
105 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
39 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
170 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
38 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^i1^j\;,\;i,j\...
0
votes
3answers
66 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
69 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
43 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 ...
1
vote
1answer
36 views

Recursive languages , please check whether my explain is correct?

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows. $$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$ Which of the following ...
2
votes
2answers
376 views

What are closure properties of regular languages?

In class we've been talking about DFA's and NFA's and being closed under ____. The homework problems say to "use closure properties of regular languages to show that a regular languages are closed ...
1
vote
3answers
77 views

Does the Kleene Closure of an alphabet contain an infinite string?

Suppose we have an alphabet $\Sigma$, does $\Sigma^*$ contain an infinite string? My reasoning is, since $\Sigma^*$ contains an infinite number of strings, one of those strings must have an infinite ...
0
votes
0answers
35 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?
2
votes
1answer
78 views

examples of “interesting” star-free languages

Can you point me to some examples (preferably known ones from the literature, but this is not crucial) of "interesting" / non-trivial star-free languages? I'm trying to get some intuitive sense of ...
-1
votes
2answers
62 views

Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular [closed]

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove ...
2
votes
0answers
51 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 ...
0
votes
0answers
35 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
1
vote
2answers
57 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?
1
vote
1answer
27 views

Creating a regex expression for a regular language

$\{x \in \{0, 1 \} : x = 0^m1^n \hspace{.1cm} \text{for some} \hspace{.1cm} m, n \in N \hspace{.1cm} \text{such that} \hspace{.1cm} m * n \ge 3\}$. I've been stuck on trying to create a regex for ...
0
votes
1answer
108 views

Math replacing natural language [closed]

Before reading any further. I ask yous to think creatively on this subject. I was in shower and was pondering over A.I. (Strong A.I. both at human level and beyond human level) as I do from time to ...
0
votes
1answer
42 views

proving a implication with regular expressions

I'm trying to prove the following implication to be false: R*(T+S) $\equiv$ R*(TS) $\implies$ T $\equiv$ S. Proof: We have that IF R*(T+S) $\equiv$ R*(TS) THEN T $\equiv$ S Let R, T = ∅ and S = ...
2
votes
2answers
60 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
1
vote
1answer
26 views

Using Myhill Nerode

I'm trying to prove to following language is not regular, using Myhill Nerode's theorem: $L = {a^{n^2}}$ I found this: $a^n$ (has no equivalence classes to) $a^m$ when n ≠ m because $a^na^n$ is ...
1
vote
1answer
110 views

Arden rule proof

I'm studying Arden's Rule for regular languages, but I'm having troubles with the proof. Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation ...
2
votes
0answers
33 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 ...
1
vote
2answers
34 views

What are some quick things to look for to see if a language is regular or context-free

Without using proofs or pumping lemma, but just by looking at the given language by eye, what are some quick tips and techniques that can be used to see that a language is regular, or that a language ...
1
vote
1answer
36 views

Is Σ* the same as saying L*

I'm getting confused over the two. Are they the same? The complement of a language L is Σ* - L. Is saying L* - L wrong?
4
votes
3answers
431 views

Number of states in a finite automaton

How many states are required by a deterministic finite automaton to store $m$ words each of length $n$? I came across $2^{mn}$ as the solution but there was no explanation.
1
vote
1answer
12 views

Regular and not regular based on the value of n

If $L = \{a^nb^n, n \leq 100\}$ is regular, is $L_2 = \{a^nb^n, n > 100\}$ also regular? $L$ is regular because we can draw an FA(finite automata) for it. It's not possible to draw an FA for $L_2$,...
0
votes
2answers
38 views

Why is the below language regular?

If I have a language $$L=\left\{wxwy : w,x,y \in \{a,b\}^+ \right\}$$ I am not getting how come we are able to write regular expression for this of the form $$a(a+b)^+ a(a+b) ^+ + b(a+b)^+ b(a+b) ...
1
vote
0answers
41 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
1answer
45 views

Product of two DFA.

Let $ A, B \subset \{ a, b\}^* $ and $A, B$ be regular. Lets define: $ A \circ B = \{ w \in A | \exists y \in B , \#_aw = \#_ay \}$ where,for example: for $ w = aaabaaba$ $\#_aw = 6, \#_bw = 2 $ ...