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-language]

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.

1
vote
1answer
37 views

String powers. Lemma 1.3.5 in word processing in groups. Epstein.

I can't understand this demonstration. Why if ${w'}_1$ is different from ´${w'}_2$ then we have that $f(u)$ and $v'$ are powers of some string $z$?
2
votes
1answer
32 views

What is open first in formal languages

What is a set of values that come from $(1^*0^*)^*$? Is it set of any number of combinations of any number of 1 and any number of 0. Like we have 10 inside of brackets and than repeat it as much as ...
0
votes
1answer
46 views

Simply starred language. $\left\{(ab)^n:n\in\mathbb{N}\right\}$ it is regular?

I have many doubts with this. First: In the definition, let $A=\left\{x\right\}$ one-letter alphabet. Then $A^{\ast}$ is simply starred? Second: In the definition, I know that $\left\{a^nb^n: n \in \...
0
votes
1answer
37 views

square-free word

I am trying to understand one concept. Is it possible to have a square-free(no subwords ss) word in a language of just $\{0,1\}$ of any given length ( $10^{100}$ for instance). I found out a Thue–...
1
vote
1answer
13 views

Proving commutativeness of an operator using structural induction

Let's suppose we have this language that defines natural numbers: $$ \Bbb{N} = O : S \Bbb{N}$$ So a number can either be $O$ (zero) or $S \Bbb{N}$ (the successor of a natural). Let's define the ...
-1
votes
0answers
20 views

On deterministic automaton on an alphabet of a letter.

The book is: Word processing in groups by author Epstein Why if $n$ is the period, the language $L$ accepted by the automaton is $L_1\cup (x^n)^{\ast}L_2$? How to deduce that $L_1=\left\{\epsilon, x^...
2
votes
1answer
26 views

Is it ALWAYS true that if L= {w|odd(w) is regular} then L is regular.

I have been stuck on this problem for a couple of hours and can't seem to figure it out.A bit of a hand would be nice.So we have that odd(w) is the letters from the string w that are in odd positions ...
0
votes
1answer
24 views

Finite automata where the difference in the number of a's and b's is less than three

Given the following problem: Design a finite automata that only recognizes the strings of the language $L$ of the alphabet $\sum = \{ a, b \}$ such that each string does not contain any prefixes ...
2
votes
1answer
29 views

Given a finite automaton determine if it is deterministic and indicate regular expression

Given the finite automaton: Make the transition table and indicate if it is deterministic or not. Indicate which of the following regular expressions corresponds to the language recognized by the ...
0
votes
1answer
60 views

Prove that $L= \{w|$ $w $ ends with a palindrome of length greater than or equal to $4\}$ is nonregular using the pumping lemma.

The alphabet is $\{a, b\}$ Hi, I tried this: Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is ...
0
votes
1answer
27 views

Regular expression: Difference between $\emptyset$-concate and $\lambda$-concate?

Given the definition below, is that the concatenation $\emptyset A$ the same as $\lambda A,$ given $A$ a regular expression? If not, what's the difference? My guess is that if I take concatenation $AB$...
0
votes
2answers
36 views

What is regular expression and its NFA of a word that accept any number that is divisible by 5?

I was given a task to find RE and NFA for a word that is divisible by 5. ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} String passed to RE could be of any length You may ...
0
votes
1answer
48 views

Prove $L$ is context free if $L_1$, $L_2$, $L_3$ are regular by building a suitable grammar

Given $L_1$, $L_2$, $L_3$ are regular, prove that: $$L=\{w_1w_2w_3\space|\space w_i\in L_i\space \land\space|w_1|+|w_2|=|w_3| \}$$ is context free by building a suitable context free grammar. I know ...
0
votes
1answer
26 views

Prove that language that has unequal 0's and 1's is not regular

Given the language L { w | w has unequal number of 0's and 1's } show that it's not regular. I tried to use pumping lemma choosing the word of the form $0^p$ $1^{2p}$ ensuring that we'll have to pump ...
1
vote
1answer
22 views

How to prove that a language which clones is regular?

I am trying to prove that the following language is regular: $L'$ is a clone of $L$ where $L$ is a regular language over $\{0,1\}^*$. For example, if $L=001$, then $L'=000011$. If $L=010$, $L'=001100$...
0
votes
1answer
49 views

Please help me with this regular expressions

I'm 100% sure that both these regular expressions are same since it produces an exactly same set of strings, but I'm unable to prove it mathematically. Can someone please provide me with a step by ...
1
vote
1answer
44 views

Is it semi-decidable whether a context-free grammar generates a regular language?

It is a well-known that it is undecidable in general whether an arbitrary context-free grammar generates a regular language. However, I could not find any results concerning the question whether this ...
1
vote
3answers
28 views

Why is this language not Regular - w^Rw (i.e. a word concat. with its reverse)?

Consider the language L = {$w^R w$ | $w \in \{a,b\}^* $} - why is this not regular? I'm very new to the idea of formal languages and computer science, so I've likely missed something basic. However, ...
0
votes
0answers
32 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 ...
1
vote
1answer
38 views

i really don't know how to get $s = xyz$ for pumping lemma for this language

Let $L=\{a^i b^j c^k d^l : i, j, k, l > 0, 3(i+j) \geq 2(k+l)\}$. Proof that this language is not a regular language. I have no clue, cause i can't find any example for $3(i+j) \geq 2(k+l)$ or ...
1
vote
1answer
29 views

String sets commutative under concatenation

Given A and B, string sets included in the Kleene closure of the same alphabet, say something about their nature (are they the same, or somehow interlinked by a simple set concatenation?) if AB = BA (...
0
votes
1answer
31 views

$A= \{w \in \{a, b\}^∗ \mid \text{length of $a \leqslant 5$ and length of $b \leqslant 20$}\}$

I came across this proof-question to check the regularity of the following language: $A= \{w \in \{a, b\}^∗ \mid \text{length of $a \leqslant 5$ and length of $b \leqslant 20$}\}$ I tried first ...
1
vote
2answers
65 views

What is wrong with my application of the Myhill-Nerode theorem on this language?

Let $L=\left\{ w\in\Sigma^{*}\mid w\text{ has an equal number of 01 and 10}\right\}$ (e.g. $010\in L$) over $\Sigma=\left\{ 0,1\right\} $ I initially tried to prove that $L$ is not regular Proof:...
1
vote
1answer
20 views

Design DFA for $ (a + b(ba)^*)^*b$

I'm having some trouble to design a DFA that accepts the language defined by this regular expression $(a + b(ba)^*)^*b$ Can I say that $(a + b(ba)^*)^*$ is the same as $(a + b)^*$ ? Given this ...
0
votes
1answer
64 views

Prove that every infinite regular language has an undecidable infinite subset

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 ...
1
vote
1answer
22 views

Generalizing Regular Expression from FAs

if we want to generate a regular language for this FA, it would be (1 ∪ 0(00 ∪ 11)* (01 ∪ 10)) ◦ ((00 ∪ 11) ∪ (01 ∪ 10)(00 ∪ 11)* (01 ∪ 10))* Let's challenge ...
1
vote
0answers
21 views

Proving that $L=\{xww^r\mid x,w \in \{0,1\}^+\}$ is not regular

In the alphabet $\Sigma=\{0,1\}$, I need to prove that this language is not regular. I've tried using the pumping lemma, choosing the string $a(ab)^p(ba)^p$ for a given $p$, any possible choose of a ...
0
votes
1answer
61 views

Regular languages: Prove $2^n + n < 2^{n+1}$ for $n \ge 1$

I was trying to use the pumping lemma to prove that the language, $ \{ 0^N | \ n $ is a power of 2$ \}$, is not regular. Assume to the contrary that the language is regular. Let p be the pumping ...
1
vote
2answers
68 views

Write a minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$

Write a minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$ My attempt: I currently haven't completed the solution, but my main problem is to find a simpler solution for this as the ...
0
votes
0answers
15 views

q can be reached from R by traveling along 0 or more ε arrows

This is from book, Introduction-To-The-Theory-Of-Computation-Michael-Sipser, Third Edition, P56. Now we need to consider the ε arrows. To do so, we set up an extra bit of notation. For any state R of ...
0
votes
1answer
144 views

Let G be the language of all string over {0,1} that do not contain a pair of 1s that are separated by a odd number of symbols.

This is a questions in book, Introduction-To-The-Theory-Of-Computation-Michael-Sipse, Third edition, P85. This is not hw problem(solution is given) So based on the given hit, we negate it first as F'=...
0
votes
0answers
33 views

Regular expression from right linear grammar or from automata

I have the following grammar: \begin{array}{lcl} G & = & (X,V,S,P) \\ X & = & \{ 0,1,2 \} \\ V & = & \{ S,A,B \} \end{array} $$P = \left \{ \begin{array}{lcl} S &\...
-2
votes
1answer
29 views

Show that $L^D = \{ ww \mid w \in \{a, b\}^* \}$ may not be regular. [closed]

Suppose that $L$ is a regular language over the alphabet $\Sigma = \{a, b\}$. Show that $L^R = \{w^R \mid w \in L\}$ is regular ($R$ means reverse order). However, show that $L^D = \left\{ww \mid w ∈ \...
0
votes
1answer
29 views

Design a Deterministic Finite Automata (DFA) for 'abab'

Problem Design a deterministic finite automata (dfa) that satisfies the following: { w | w has 'abab' as a substring} Hence, ...
1
vote
1answer
20 views

* on empty string

we know that {a,b}* = { ε, ab, abab, ab, a...}. and ∅* = {ε}. what about ε*. My thinking is that since * is regular operation, not string operation, which means we can't apply * on empty string. ...
0
votes
1answer
28 views

Regular expression operations

Please, please check my work. Given alphabet $\{a,b\}$. Instead asking conceptional questions to confirm my understand, I use some example. Regular expression : $(a \cup b^*)(b \cup a^*)$ We have ...
2
votes
2answers
42 views

is a fractional i allowed in pumping lemma??

I checked the pumping lemma in many books(introduction to the theory of computation Michael Sipser) and website(wikipedia). they all give the same explanation:(definition from introduction to the ...
1
vote
2answers
101 views

Regular Expression VS Finite Automata

I am having a hard time to follow a concept from Introduction to the theory of computation (3rd ed.) by Michael Sipser. I got confused by the last sentence. Ok, we can convert regular express into ...
1
vote
2answers
130 views

How to find Myhill-Nerode equivalence classes, algorithmically?

Say I have a regular expression given, or a language given in set form. Examples: $$ L= \{ w \in \{a,b\}^* | w \ \text{ matches} \ \ a^*b^*(bab)^*\} \\ L = \{ w | count_a(w) = 5 \} \\ L= \{ w \in \...
2
votes
1answer
58 views

Given regular language $L,$ prove $L'$ is regular

Given that $L$ is a regular language over some alphabet $\Sigma,$ prove that the language $L'=\{x_1x_2\cdots x_k\ |\ x_1,\dots ,x_k \in \Sigma\ \land \exists y_1,y_2,\dots y_{2k} \in \Sigma , \ ...
0
votes
1answer
59 views

Proving language is not regular using pumping lemma

Show that the language                     $L =$$\left \{ a^{n!} : n\geq 1 \right \}$ is not regular using pumping lemma My solution is : Suppose L is regular There exist some pumping length for L,...
1
vote
0answers
26 views

PL to prove a language is not regular

Prove that the following language L over alphabet $\{1\}$ is not regular. $L = \{w \mid |w| = k, \text{ where } k \text{ is a prime number}\}$ Suppose the language is regular for contradiction. Since ...
0
votes
0answers
19 views

To show that language is not regular using pumping lemma

L = $\left \{ a^{n}b^{n} : n \geq1 \right \}\cup \left\{a^{n}b^{n+2}: n \geq1\right \}$      L = $\left \{ a^{n}b^{n}(\lambda+bb) : n \geq1 \right \}$      Assuming L is a regular language. Let p be ...
2
votes
0answers
63 views

A simple example in regular categorical logic

I am starting to learn about regular categorical logic as an application of what we learned in class about regular categories. After reading through the definitions of the representation of terms, ...
0
votes
2answers
64 views

$L_1$ is a regular language, $L_2$ is a non-regular language, the intersection $L_1 \cap L_2$ is finite language

1) Given $L_1$ is a regular language and $L_2$ is a non-regular language, the intersection of $L_1$ and $L_2$ is a finite language, how to prove that the union of $L_1$ and $L_2$ is a non-regular ...
0
votes
1answer
38 views

Are addition expressions a regular language?

For an alphabet $\Sigma = \{1, +, =\}$ and language $L= \{ 1^m +1^n =1^{m+n} | m, n ∈ \mathbb{N} \}$, is $L$ regular? So here are my thoughts: I do not believe this language is regular. This is ...
1
vote
1answer
132 views

Regular expression for roman numerals

I am trying to construct a regular expression describing the roman numerals less than 2,000 (excluding $0$ using the alphabet $\{ M,D,C,L,X,V,I\}$. Here are my thoughts: We can divide our task into ...
0
votes
1answer
41 views

$|L^k| = |L|^k$?

I am trying to prove that $L$ is a nonempty finite language and $k$ is a positive natural number then $|L^k| = |L|^k$ where $|L|^k$ refers to the cardinality of $L$ raised to the $k$th power and $|L^k|...
1
vote
1answer
174 views

Find an automaton that recognizes this language

The exercise is copied literally, and asks to find an automaton that recognizes the language described by the regular expression $a{(bab\vee a)}^\ast b$. I have no idea how to start. Any help? ...
0
votes
2answers
48 views

How to prove that a transformed language is regular using an NFA

I am trying to prove a transformed language plus(L), which transforms a binary of an integer to a binary of n+1. So ...