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
44 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 ...
-3
votes
2answers
27 views

induction odd length of 1's automato

Consider the following automaton, $A$. diagram I tried using the method of induction to prove that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. and to Show that there ...
1
vote
1answer
21 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 } ...
1
vote
1answer
513 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
votes
2answers
33 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 ...
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$?
1
vote
1answer
19 views
0
votes
0answers
16 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
28 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: ...
3
votes
1answer
48 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 ...
1
vote
2answers
36 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
28 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 ...
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.
1
vote
1answer
398 views

Pumping lemma proof of $L = \{a^nb^m \mid 0\leq n<m\}$

Prove the following language is not regular using the pummping lemma $L = \{a^nb^m \mid 0\leq n<m\}$ I tried solving this problem what I don't think I was able to reach an accurate proof. But this ...
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
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
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 ...
31
votes
8answers
4k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
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
3answers
670 views

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
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
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 ...
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 ...
4
votes
1answer
466 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} ...
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 ...
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 ...
0
votes
1answer
98 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 ...
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.
0
votes
1answer
467 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 ...
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
16 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
48 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
54 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 ...
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?
0
votes
2answers
140 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
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
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
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 ...
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
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 ...
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, ...
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 ...