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

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
102 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
29 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
51 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
57 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
51 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
62 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
34 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
44 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
55 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 be ...
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
47 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
72 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
32 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
35 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
40 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
47 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
70 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 } ...
0
votes
1answer
19 views

power + operator for binary

What is the specific definition for power $+$ operator in automata theory? For example, when $x$ is a binary what does it mean that $x = 0^+$. Does it mean that x is a string with at least one $0$?
0
votes
3answers
46 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
1answer
24 views

What is the language recognized by the following deterministic finite-state automaton?

Is the answer: {w : w ∈ {0*,1*} and w contains at least 3 zero} correct?
0
votes
0answers
24 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
1answer
30 views

Regular expression,

Question 23: The string zyyzy belong to the language, right?
1
vote
1answer
32 views

Finite Automata for regular expression

I am trying to construct finite automata for this regular expression: Every block consisting of 5 characters need to contain at least two zeros. The regular expression would look sth like this: (00(1|...
1
vote
2answers
64 views

Binary Strings: How to determine if decomposition is ambiguous

Let's say I have the following decomposition: $$\{100,10011,00110\}^*$$ How would I determine if the decomposition is ambiguous or unambiguous?
1
vote
1answer
53 views

Pumping Lemma clarification, and regularity of language of equal number of zeros and ones.

All explanations and proofs I find about the Pumping Lemma are ambiguous. So if I understand this correctly, if we can find some $p>0$, then for any string $|w| \ge p$, we should be able to split ...
3
votes
1answer
99 views

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$? My attempt : Input set is given. So, we have 3 parts of DFA which we can change: Start state Transition Function Final ...
0
votes
1answer
28 views

Need a hint for a proof using the pumping lemma that a language is not regular

Currently I am stuck at a proof of : $A_2=\{w001;|w|_0<|w|_1 \wedge w\in \sum^*\}$ unsing only the pumping lemma. Can you give me a hint for a good start? thanks in advance.
1
vote
1answer
28 views

How to proof using only pumping lemma that something is not regular?

In formal languages I need to proof using the pumping lemma that the following is not regular: $A_1=\{1^m0^n10^n|n,m\in \mathbb{N}\}$ How to achieve that? Any help is upvotet
1
vote
1answer
67 views

Proving L is regular or not using pumping lemma

So I'm trying to prove that the language L = {$1^n$ | n is composite} is either regular or non-regular using the pumping lemma. I wanted to ask if I'm on the right track. So I assume that L is ...
2
votes
1answer
54 views

Is the complement of a given language context-free?

I have a problem with finding out if the complement of language L is context free. $L = \{ ww : w \in \{a,b\}^{*} \wedge \text{ }w \text{ number of }a\text{'s in }w \equiv \text{number of }b\text{'s ...
0
votes
1answer
50 views

Prove that if $L$ is regular, then $f(L)$ is regular too

Prove that if $L$ is regular, then $f(L)$ is regular too. $\Sigma_1$ and $\Sigma_2$ are two arbitrary alphabets, $f$ is a function that maps every symbol of $\Sigma_1$ to an element in $\Sigma_2$, i....
0
votes
1answer
68 views

For a language $L$ is $Double(L)=\{w: ww\in L\}$ regular? [duplicate]

Given a language $L$, let $Double(L)=\{w: ww\in L\}$ and $NotDouble(L)=\{w: ww\notin L\}$ If L is regular, are $Double(L)$ and $NotDouble(L)$ regular? I tried using the closure properties of $L_{reg}$...
2
votes
2answers
86 views

formal languages - why is this regular?

I'm studying for a test on formal languages and automata. I came upon the following question (translating, so i apologize for the non-formal english): $L_1$ is the language composed of all words ...
0
votes
1answer
17 views

String recursive definition corner case

I need your assistance with a corner case of this problem: Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}. I've ...
0
votes
1answer
68 views

What is the nature of given language?

$$L=\{a^n b^n :n\geq0, n\neq100 \}$$ I just wanted to know that through pda. How will we make sure that $n\neq100$ or say I put a restriction that $n\geq100$. How to design a PDA using these ...
1
vote
1answer
57 views

Question about deterministic finite automaton and accepting states

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the set of the languages that can be accepted by "$1-$DFA" is a subset of the ...
1
vote
1answer
76 views

Question about deterministic finite automaton (DFA) [closed]

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the language $\mathcal L=\{0,00,0000\}$ cannot be accepted by any $2-$DFA.
2
votes
1answer
65 views

Representation of regular languages by monoids [closed]

I'm interested in representation of regular languages by monoids, and in particular of how to use this kind of representation to get a recognizer. I have found some references on the web, but does ...
1
vote
1answer
61 views

Language with middle third removed

Originating from Sipser's book: Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed. The solution I came across makes the ...
0
votes
2answers
34 views

which of these languages are regular sets?

$$ L_1 = \{a^p b^q\ |\ p+q \ge 10^6\} \\ L_2 = \{a^m b^n\ |\ m-n \ge 10^6\} $$ According to me both of these languages require comparison between number of $a$'s and $b$'s so both of them should ...
0
votes
1answer
18 views

Determining whether a given language is regular, and finding a regular expression

I know there are a lot of questions similar to this one, Proving a language is regular is just one example. However, I have not managed to find an answer that really answers my question. I'm currently ...
0
votes
1answer
102 views

Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

My question originates from Sipser's book. Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define: NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A} NOEXTEND(A) ...
1
vote
1answer
22 views

Construction of DFA using an odd bit of language

I am working through a lecture and it constructs a DFA using the language: $$\{w\mid w\textsf{ is any string not in }(ab^+)^\ast\}$$ What does the $(ab^+)$ mean?
1
vote
1answer
60 views

If $A$ is regular, is the language $\{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$ regular?

Here is the question: Let $A$ be any regular set over some alphabet $\Sigma$. Is the language $$ L = \{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\} $$ necessarily regular? I am unable to ...