Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

0
votes
0answers
17 views

Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
1
vote
1answer
46 views

If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language?

Let $L = \{ a^{2^n} \mid n \ge 0 \}$, which is a non-regular language (no proof here). Let $M = (\Sigma,Q,\delta,z_0,F)$ be a DFA with $\Sigma = \{a\}$, $Q = \{z_0\}$, $\delta(z_0, a) = z_0$ and $F = \...
2
votes
1answer
78 views

Language of all words accepted by a TM by at most $t$ steps is regular

Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$ $L = \{ w \in \Sigma^* : w$ is accepted by $M$ by at most $t$ steps$\}$ I want to show that $L$ is regular. My attempt: I'm ...
0
votes
0answers
31 views

Show that the set $\{uv | u \in L \ and\ v \notin L\}$ is regular

The full question is: Let $L$ be a regular language over $\{a, b, c\}$. Show that the set $\{uv\ |\ u \in L \ and\ v \notin L\}$ is regular I have the following answer, but I'm not sure if it's ...
0
votes
0answers
112 views

When proof by induction on length string is not possible?

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ...
2
votes
2answers
51 views

Closure of context-free languages under regular quotient [duplicate]

Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \{w| \exists x \in R: wx \in C\}$ is also a context-free language?
4
votes
1answer
535 views

Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
2
votes
1answer
41 views

Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?

If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪ (rs)*. I think this is not true. And I believe this would always be true : (r ∪ s)* = r* ∪ s* I wanted to clarify this ...
4
votes
1answer
83 views

The equational theory of regular languages has no finite set of axioms for general alphabets

According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms. Why does this imply that it has no finite set of ...
0
votes
0answers
20 views

Is there any algorithmic way to decide the equivalence classes in the nerode relation?

Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$ The Nerode relation $R_L$ says $xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$ By looking at the language : I can conclude ...
2
votes
1answer
42 views

If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?

I am confused interpreting the statement of this question: "If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?" Should the symbol "|" (such as) be understood as ...
0
votes
0answers
18 views

Prove that every infinite regular language has an undecidable infinite subset [duplicate]

I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due ...
0
votes
0answers
17 views

Trouble coming up with an expression to describe a DFA [duplicate]

This is a DFA that describes a language over {a,b} that only accepts a string if the number of a's in the string is not divisible by 3. I'm having difficulty coming up with an expression for it, I'm ...
1
vote
1answer
92 views

Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results

I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment. $\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$ $\text{Prove ...
3
votes
2answers
66 views

The language of non-extendable strings of a regular language is regular

I recently came across this question in my textbook. $ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $ $ \text{Prove that the language is also ...
1
vote
1answer
65 views

Proving that a Language is non-Regular

Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular. I was wondering if my intuition holds for proving this language as not regular: Let $q = \max(i, j) - \min(i, j)$. ...
0
votes
1answer
78 views

Show that C(n) = {a^k | k is a multiple of n} is a regular language

I came across this question in an exam book and was unable to find a solution: Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1. I wasn't able to ...
1
vote
1answer
31 views

Proving that language is regular or not [duplicate]

How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not: $\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$ I started with the ...
-1
votes
1answer
56 views

Prove or disprove whether L is regular by definiton [duplicate]

Assume L is regular language, define 𝐿1 = {𝑣𝑤: 𝑣 ∈ 𝐿,𝑤 ∉ 𝐿}, prove or dispute L1 regular or not ?
3
votes
2answers
44 views

variable exponent in expression of a formal language

Take a look at the following expression: {(AnB)m|n>0,m>0} Or, to put it simply: the words in the language, have repeating parts consisting of, some A's followed by a single B. There are TWO school ...
1
vote
1answer
53 views

Prove that A is non-regular using K-Complexity Non regularity theorem

Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$ Given $A \...
1
vote
1answer
42 views

Decide whether this language is regular

Decide whether the language $L$, defined by the following grammar is regular or not: $S \rightarrow aab$ $S \rightarrow aacSb$ $S \rightarrow acSab$ $S \rightarrow acSacSb$ Where should I start? I ...
1
vote
1answer
103 views

Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)

When proving a language is non regular we can use Kolmogorov complexity. As far I know to do this we just have to use this satisfy the following conditions Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (...
0
votes
1answer
49 views

All finite languages can be decribed using a regular expression? [duplicate]

I have a question. All finite languages can be decribed using a regular expression?
-1
votes
1answer
168 views

Regular expression of a language over {a,b} which does not contain substring bbb [duplicate]

I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.
0
votes
1answer
313 views

Using Myhill-Nerode to prove that language is not regular

L = {$xy ∈ \{a, b\}^∗ : |x| = |y|$ and x contains the substring aa} I am trying to prove that this language is not regular using MyHill-Nerode theorem but I am unable to find equivelance classes of ...
0
votes
0answers
69 views

Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
3
votes
2answers
83 views

Constructive Proof on Regular Languages

As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages. $$L_1=\{w│w^R∈A\}$$ $$L_2=\{w│w=a_1 b_1,…,...
2
votes
1answer
75 views

Is there a way to find a simple regular expression for this language?

Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is ...
0
votes
1answer
46 views

Show that the regular language is contained in another

Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product. $L_1^+ \bigotimes L_2^+$ ...
0
votes
3answers
2k views

DFA for Strings with third symbol from RHS as 1

How can we make a DFA for given condition in title from alphabets {0,1} (binary). What can be the regular expression for this? My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'...
0
votes
0answers
84 views

Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
0
votes
2answers
240 views

Regular expression for string with substring 010 and ending with 01

How can one design a regular expression for given string in title ? Also how can we draw DFA of that regular expression? I've tried many expressions but couldn't succeed, please help.
5
votes
2answers
66 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
0
votes
1answer
104 views

Do all Regular Expressions describe Regular Languages?

I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent ...
2
votes
1answer
182 views

Concatenation of two regular languages

In a question, it is given that L is a finite language over the unary alphabet and L+ is not regular. We know that L+ = LL* Since L is finite, it must be regular because all finite languages are ...
2
votes
1answer
272 views

Prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular

We have to prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular. Attempt: We assume that the language is regular. Thus it would satisfy ...
3
votes
1answer
85 views

Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)

I'm stuck with another homework question - "Design an NFA with $n$ states such that the corresponding equivalent DFA constructed using the subset-construction method has less than $n$ states." What I ...
2
votes
1answer
159 views

Is set of all regular languages on a specific alphabet a regular language?

so i know that the set of all strings over any finite alphabet is countable, but this question is different so if our language is set of all regular languages(or set of all regular expressions) on a ...
1
vote
1answer
168 views

Finding the regular expression equivalent for the given finite automaton

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression. On inspecting the given automata, I started deducing the ...
0
votes
1answer
59 views

Can someone give a generic definition of any Definite Language in set builder notation?

What I have come across as a definition is - a language $L ⊆ Σ^*$ is said to be definite if and only if $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$ Using these questions - Show that every ...
1
vote
2answers
215 views

What are definite languages? How do you formally define them?

I have a question in my homework that deals with the concept of a definite language. The question defines a definite language as follows - "A language L is definite if there is some k(> 0) such that ...
1
vote
1answer
265 views

How do you convert a regular expression to its disjunctive normal form?

A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, ...
0
votes
0answers
44 views

Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
2
votes
2answers
255 views

Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite? [duplicate]

Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma? Additionally,is there an ...
1
vote
0answers
57 views

Definition/properties of NFA extended transition function [closed]

I am trying to prove by induction that if $$\hat\delta_d(q_0, w) = \hat\delta_n(q_0, w)$$ I know by practicing inductive proofs of the $\hat\delta$ for DFAs, that on the basis of the definition of $...
2
votes
2answers
145 views

Decision problem for a Regular Langauge

I'm not sure if my logic is correct when it comes to the algorithm for decision problems. The concept is confusing me when I fail to distinguish its answer from that of a proof. For example: Given ...
1
vote
1answer
36 views

Meaning of # in descriptions of languages

This is a very simple question, but I cannot find the answer anywhere, mostly because I don't know how else to ask about what I'm looking for. I have a homework assignment that has to do with pumping ...
0
votes
1answer
37 views

Given a regular language $U$, when does there exist $V$ such that $U^\omega$ = $\lim V$?

What I know is that $W = \lim V$ for some $V$ if and only if $W$ is the language of some deterministic buchi automata, namely that of $V$. So, to attack this problem I tried to come up with some ...
1
vote
2answers
126 views

DFA Infiniteness Testing

Why is it that the test for an infinite language on the DFA $M$ has an upper bound of $2n$? That is to say, when testing for a string of length $k$, why does the theorem say: $$n \leq k < 2n$$ I ...