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
1answer
21 views

Proving that a certain language is regular

Consider two languages $L$ and $\operatorname{minimum}(L) = \{ w \in \Sigma^* \mid w \in L, \text{ but no real prefix of $w$ is in $L$}\}$. I want to prove now, that for every DFA language $L$ , ...
4
votes
2answers
35 views

Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
2
votes
1answer
30 views

Show that $L = \{a^p b^q \mid p, q \in \mathbb{N}^0 \setminus \mathbb{P}\}$ is not regular

Full disclosure: this is a homework question, so I'm only looking for a kick in the right direction. The original question notes that $\{a^p \mid \ p \in \mathbb{P}\}$ is not regular and that the ...
1
vote
1answer
27 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
1
vote
1answer
32 views

Infinite recursive languages and infinite regular languages.

Could the following statement be correct? "Every infinite recursive language has as a subset an infinite regular language."
1
vote
2answers
29 views

NFA to DFA for odd a's and even b's

The regular expression for accepting odd a's and even b's I calculated is: (aa)*a(bb)* and the NFA: ...
5
votes
2answers
41 views

Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
0
votes
1answer
75 views

Pumping Lemma - non regular

Can everyone help me to show that: the language $$L = \{a,b\}^* \setminus \{a^m b^{2m} a^n\mid m,n \ge 0\}$$ is not regular. I don't know what is the meaning for the proof.
0
votes
3answers
42 views

Where did I go wrong creating a Deterministic finite automaton?

My goal was to create a Deterministic finite automaton that handled the regular language (00010 + 1101 + 1010)* and had a parity bit at the end to make sure 0's where even. To clarify what I mean by ...
0
votes
1answer
27 views

Finding a Regular Grammar

so I have to find a regular grammar to generate the following sets: $(1)$ $\{aa, ab, ac\}$ $(2)$ $\{ab^n,ba^n\mid n\ge 0\}$ $(3)$ $\{ab^{2n}\mid n\ge0\}$ I'm wondering if anyone can check my ...
2
votes
1answer
38 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 ...
0
votes
1answer
23 views

Prove that $even(L)$ is regular

For any string $w$, define $even(w)$ to be the string that results from deleting all the letters that occur in odd positions of $w$. For example, $even(a)=ε$, $even(ab)=b$, $even(acb) = c$, and ...
1
vote
1answer
66 views

Is the language of complex numbers regular?

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ ...
0
votes
1answer
18 views

If $L_1.L_2$ is regular, and $L_1$ is regular, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. Now, Is this true? Assume that $L=L_1.L_2$ is a regular language. Also ...
1
vote
1answer
46 views

Find an LL(2) grammar for the following language

The question asks to find both an LL(1) and an LL(2) grammar for the following language {𝑎^𝑚 𝑏^𝑛 𝑐^𝑚+𝑛 | m,n ϵ N} I have an LL(1) grammar like so ...
0
votes
1answer
13 views

regular languages ,context free grammer.

I know that if a language is regular then it is context free. and i know also that the class of regular languages are closed under intersection. Now, Lets say we have two languages that are not ...
3
votes
2answers
33 views

subsets of non regular language

I know that there are many languages that are context free but not regular like $\{a^n b^n :n>0\}.$ But I want to know if every context free but non-regular language has infinitely many non-regular ...
0
votes
1answer
18 views

A regular expression for the language $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$

A language like $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$ is given. The first question : Is this language regular? The second question : If $L$ is regular, How can we write a regular ...
0
votes
1answer
12 views

Which language L have exactly one equivalence class

Consider the alphabet {a,b}, for which language does the equivalence relation R have exactly one equivalence class? From what i understand about equivalence class, each state is consider a class. So ...
1
vote
1answer
30 views

Finding the language of a finite automaton

Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is $L(A) = (a ...
0
votes
1answer
31 views

How do I describe the following DFA

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n($ w $) denote the number represented by $ w $: ...
0
votes
1answer
24 views

A regular expression for the language $L=\{w:(n_a(w)-n_b(w))mod3=1\}$

Assume a language like $L=\{w:(n_a(w)-n_b(w))mod3=1\}$ is given. How can i find a regular expression for this language using a systematic process? Note : I can easily draw a DFA accepting this ...
0
votes
1answer
15 views

If $L_1 \cup L_2$ is regular and $L_1$ is a finite language, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. So, Assume that we have a regular language like $L=L_1 \cup L_2$ and we ...
0
votes
1answer
49 views

Regular expression of the set of strings of even length

I should try to write a regular expression of the set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. If string has even length, and if we have one $k$; there should be (odd ...
1
vote
1answer
167 views

Regular expressions represents the sets provided

While I am studying formal languages, I see these questions.What are the answers for them? a) The set of strings over {a, b, c} that begin with a, contain exactly two b’s, and end with cc. b) The ...
0
votes
3answers
238 views

The family of regular languages

Is the family of regular languages closed under countable infinite unions? If so prove it, If not give a counterexample.
0
votes
1answer
253 views

Is the family of regular languages closed under the operation of set difference?

Prove that the family of regular languages is closed under the operation of set difference. (I tried coming up with an NFA that will recognize the new language, but I get stuck with defining the ...
3
votes
1answer
23 views

Language of binary multiplications relation.

Given $\Sigma = \lbrace 0, 1 \rbrace$ and $L \subseteq (\Sigma \times \Sigma \times \Sigma)^*$. Let $first(w), second(w), third(w)$ be word from $(\Sigma \times \Sigma \times \Sigma)^*$ limited to ...
0
votes
1answer
67 views

Converting right-linear grammar to left-linear grammar

I have the following language: $$L := \{b(ab)^n a^m \mid n, m \geq 0\}$$ and have created a right-linear grammar: Grammar $G(b(ab)^n a^m)$ Terminals $a, b$ Non-terminals $S, S_1, ...
1
vote
1answer
12 views

Defining a right-linear grammar for a language

Would someone please be able to confirm if my right-linear grammar is correct for the language L? $L := {b(ab)^na^m | n, m \ge 0}$ Grammar $G(b(ab)^na^m)$ Terminal a,b Non-terminal S, S1, ...
0
votes
1answer
28 views

Identifying a regular language

I'm currently trying to answer a question were I have to confirm if a language is regular or not. If the language is not regular I have to give an informal answer to why the language is not regular ...
1
vote
2answers
48 views

Using Pumping Lemma to prove a language not regular

I'm currently stuck on a problem were I'm asked to look at a language and prove whether or not it is a regular language or something else such as context-free. I've been given the example: ...
1
vote
1answer
51 views

How to check if a language is regular

I'm currently studying a formal languages & automate module on my course and I have been asked to answer the following question: Which of the languages below are regular? If the language is ...
1
vote
4answers
41 views

Regular expressions: Show that A*B is the solution of X = AX + B

I'm currently working on the following problem for my computer theory class. It goes as follows: Let $A$ and $B$ be regular expressions. Show then that $A^*B$ is the solution of $X = AX + B$ ...
1
vote
1answer
54 views

Is the empty string always in a finite alphabet?

Is the empty string always an element of an aribitrary finite alphabet? I understand that the empty string is part of the Kleene-Star of any alphabet, but is it intrinsically part of any finite ...
0
votes
1answer
18 views

prove this $L$ is not regular?

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$. I want to prove that $L$ is not regular using the Pumping Lemma. So far i assumed by contradiction that $L\in REG$, so it has a pumping ...
2
votes
1answer
31 views

Regular grammar that generates a set of strings with an odd number of occurrences of a substring

This is for a homework assignment. The prompt is: Give a regular grammar that generates the set of strings over {a, b, c} with an odd number of occurrences of the substring bc. I've been stuck ...
0
votes
1answer
43 views

Regular grammar with parity

Give a regular grammar that generates the set of strings over {a, b, c} with an odd number of occurrences of the substring bc. How can you limit the number of recursions for a regular grammar to be a ...
1
vote
3answers
51 views

Proving two languages are equal

Q: Show that $\{a,b\}^* = \{a\}^*(\{b\}\{a\}^*)^*$. I am aware of the fact that both sides are sets, infinite sets actually. So for example showing that both sides are subsets of each other would ...
0
votes
3answers
38 views

is a^(m)b^(n) | m >= 99 and n>=999 a regular language?

I've been stuck on this problem for a while. Say we have the following language? a^(m)b^(n) | m >= 99 and n>=999 I'm trying to use the pumping lemma to ...
0
votes
1answer
19 views

Prove that $\delta^*(q,wv)=\delta^*(\delta^*(q,w),v)$

Imagine we have a language like $L$ with alphabet $\Sigma$ and the set of words of $L$ called $\Sigma^*$ ( notice that a word can have zero characters). We define $\delta^*$ recursively like this : ...
1
vote
1answer
41 views

A regular language that isn't pumpable?

I have moderate understanding of the lemma's use in prototypical examples like $0^n1^n$ and $WW$ (for any string $W$). I have some confusion about the lemma's application to regular languages that ...
1
vote
1answer
60 views

Regular expression for strings with even number of 1's and number of 0's divisible by 5

I am able to write a DFA for this language but don't see any good way to convert this into a regular expression. This is the DFA I came up with:
1
vote
2answers
31 views

Proving a Regular Expression

$L$ is a language from the alphabet $\Sigma = \{a,b \}$. Define $C(L)$ as another language. This language produces a $w$ as an element of $\{a,b\}^*$ with the property that there exists a $v \in L$ ...
0
votes
2answers
34 views

Is there a language like L in which $\overline {L^*} = \overline L^*$?

Assume that for every language L over the alphabet $\Sigma$, we define $L^*$ , $\overline L$ , $\Sigma^*$ & $L^n$ like this : $L^n$ means joining L to itself n times. For an alphabet like ...
1
vote
1answer
38 views

Proving that reguarity is closed under prefixes?

Show that regularity is closed under prefixes. That is, if $L$ is regular, then so is $$L_1 = \{x \mid \exists y: xy\in L\}$$ I am having a hard time trying to work this through. Can you please ...
1
vote
1answer
45 views

Proving that the given language is non regular

We had a question today as follows: Let $L$ be a nonregular language and $X$ a finite set of strings from the same alphabet as $L$. (a) Prove that $L ∪ X$ is nonregular. (b) Prove that $L - X$ is ...
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 ...
0
votes
1answer
69 views

Using pumping lemma

I'm trying to prove that the language $\mathcal L = \{w \in \{0,1\}^* ∣ w \leq w′ \text{ where }w′ \text{ is any rotation of }w\}$ is not a regular language. Note: The inequality is with respect to ...
1
vote
1answer
27 views

A proof question involving a regular set and a context free language

Claim: Let $L \subseteq \Sigma^*\{\#\}\Sigma^*$ be a context-free language, where $\# \notin \Sigma$. Suppose that for each $x \in \Sigma^*$, $\{y|x\#y \in L\}$ is finite. Then $\{y|\text{ for some } ...