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
25 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
37 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
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 ...
2
votes
1answer
31 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
888 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
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 ...
4
votes
1answer
490 views

Notation of cross entropy

I have a question regarding a notation that seems to be very usual. For starters, cross entropy is defined by: \begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align} ...
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 ...
0
votes
1answer
563 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
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 ...
1
vote
1answer
85 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
0
votes
3answers
45 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: $$ ( a + b )^* a ( a + b )^* b( a + b )^* = (a + b)^* ab(a + b)^* $$ I can "see" why they are equal to ...
1
vote
3answers
45 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 ...
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
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 ...
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
13 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
3answers
728 views

Language of prefixes of regular language is regular.

Let $L$ is regular language and $L_1$ be the language of all words whose prefixes are all in $L$. I need hint to prove that $L_1$ is regular.
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
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 ...
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
254 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 ...
0
votes
1answer
69 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, ...
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 ...
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
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
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
1answer
766 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
1answer
55 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 ...
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 ...
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 ...
2
votes
1answer
35 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 ...
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 : ...