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

0
votes
1answer
17 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$?
-1
votes
2answers
31 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
17 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
14 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
27 views

Regular expression,

Question 23: The string zyyzy belong to the language, right?
1
vote
1answer
24 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: ...
1
vote
2answers
35 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
26 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
46 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
0answers
22 views

Best resources for learning about regular and context free languages

I would like to train myself when it comes to finding out if a language is regular or context free. I would be grateful for pointing what are the best places/books for training.
0
votes
1answer
25 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
23 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
40 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
42 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
41 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$, ...
-2
votes
0answers
29 views

A binary regular expression without 000 string [closed]

How to write a binary regular expression without 000 string My attempt to solve it was this 1.(001+ 1)* + 1.(010+ 1)* + (100+ 1)*
0
votes
1answer
28 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 ...
2
votes
2answers
74 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
16 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
66 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
52 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 ...
2
votes
1answer
68 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
59 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
30 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
32 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
15 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
45 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
53 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 ...
0
votes
0answers
28 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
2answers
16 views

How to prove non-regularity of a language from the non-regularity of another language?

How can I prove that $L_1=\{a^nb^m\mid n\ne m\}$ is not regular based on the fact that the language $L_2=\{a^nb^n\mid n\in\Bbb N\}$ is not regular? Thank you
1
vote
2answers
36 views

Is $L_1 = \{w ∈ {0,1}∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$ regular?

Let $L_1 = \{w ∈ \{0,1\}^∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$. Let $L_2=\{w ∈ \{0,1\}^∗ | \text{ w has at least as many ...
0
votes
1answer
29 views

Prove about $NFA$ and pumping lemma

The question: Let it be $L$ a regular language. few definitions: $p(L)$-the minimum natural number so that $L$ fulfills the pumping lemma. $n(L)$- minimal NFA that accepts $L$. $m(L)$- $Rank(L)$, the ...
1
vote
1answer
22 views

Concatenation of unknown language

$$If \space L_1L_2\space is \space regular, then \space L_2L_1 \space is\space regular$$ Is this statement correct? I can't seem to find any counter example. Besides, what is a good way of tackling ...
0
votes
2answers
15 views

Regularity of a language

$$ L = \{w \mid w \text{ does not contain } 000\} $$ $$ L_2 = \{w \mid xwy \in L \text{ for some } x,y \in (0+1)^*\} $$ Is $L_2$ regular? I am thinking regular language is closed under concatenation, ...
0
votes
1answer
21 views

Regular Pumping Lemma

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$ Determine if each language is regular ...
1
vote
0answers
22 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 ...
0
votes
1answer
25 views

Prove that relates to pumping lemma that I am not sure about

So, I will define like in my last post (for a regular language $L$): We will define $p(L)$ to be the minimal natural number so that a language $L$ fulfill the pumping lemma. We will also define ...
0
votes
0answers
23 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
1answer
15 views

Do the initial segments of the strings of a regular language form a regular language?

Let's say you have a set of strings $R$. A string $s$ is part of my language $S$ iff there is a string $r \in R$ such that $s$ is an initial segment of $r$ (you can get $s$ by removing characters from ...
0
votes
0answers
23 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?
1
vote
1answer
26 views

Cocke-Younger-Kasami (CYK) Proving a word is in a language

Using CYK algorithm I need to figure out whether the word abbabb is a word of the language of the following grammar. I think I have completed the problem correctly but I'm not sure, I'm hoping ...
0
votes
1answer
96 views

What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
0
votes
1answer
23 views

Identify the class of language?

Given a set $$S=\{x∣ \text{there is an x-block of 5's in the decimal expansion of π}\}$$ (Note: x-block is a maximal block of x successive 5's). Identify class of language? Somewhere it ...
0
votes
1answer
33 views

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: ...
1
vote
0answers
49 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 ...
0
votes
1answer
33 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr ...
1
vote
1answer
11 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
0
votes
1answer
58 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
2
votes
0answers
19 views

Writing a regular expertion for the language $L=\{0^n1^m|n\equiv m(\mod 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 ...