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
2answers
641 views

There exists a regular language A such that for all languages B, A ∩ B is regular.

There exists a regular language A such that for all languages B, A ∩ B is regular. The above given statement is true but I couldn't make any proof or find any proof. It is an objective type ...
-1
votes
0answers
22 views

regularity of concatenation of regular language

Tell me please: Regular languages are close on $', \cap, \cup, ^R,$ I consider if regular languages are closed on concanetation: $\cdot$. It seems to me that yes, because we may combine two ...
1
vote
1answer
43 views

pumping lemma - choice of partition

there is some thing in pumping lemma that I don't understand it. I think about application to prove irregularity of language. We have for each word (actual length) find partition: $xyz$ such that $\...
0
votes
0answers
17 views

Show by any method of construction that the language $A = \{a^i b^j\}$ is regular.

Show by any method of construction that the language $A = \{a^i b^j\}$ is regular. restrictions: 1) $i$ is a multiple of any given integer $n$ 2) $j$ is a multiple of any given integer $m$ 3) $n,...
0
votes
2answers
40 views

A Recursively Defined Set of Strings

Describe the strings in the set $S$ of strings over the alphabet $\Sigma = \{a,b,c\}$ which are defined recursively by: (1) $a$ is in $S$, and (2) if $x$ is in $S$, then $ax$ is in S, $xb$ is in $S$ ...
0
votes
1answer
35 views

comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
0
votes
1answer
26 views

Determine whether a given language $L$ is regular , CFL or nither.

Let $$L=\left\{w\in\{a,b,c\}^{\ast}\Bigg\vert \exists \sigma_1,\sigma_2\in\{a,b,c\}\text{ s.t } \#_{\sigma_1}(w)\ne \#_{\sigma_2}(w)\right\}$$ Determine whether $L$ is regular, context free or ...
0
votes
0answers
16 views

Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
1
vote
1answer
30 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
0
votes
2answers
58 views

How can I prove that “non-palindromes starting with 010” is not a regular language?

So, I have a language L in an alphabet $\{0, 1\}$ with each word starting with 010 and not being a palindrome. How can I prove that it is not regular? I've tried ...
0
votes
1answer
27 views

Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
0
votes
1answer
35 views

Is the language regular

We have to check, if the given two languages are regular or not. L={w |each prefix of w has more 0 than 1} L'={w|w has a prefix with more 0 than 1}. I tried something like this: If L regular, ...
0
votes
1answer
46 views

Regular language or not?

Let $L$ be a regular language over the alphabet $A=\{0, 1\}$. Is it true that the language of strings $0^n$, where binary representation of n $\in L$, is regular?
0
votes
1answer
13 views

Find the classes of given languages?

Consider the following statements $L_1 = \{wxw^R \mid w∈(a,b)^*, x∈c\}$ $L_2 = \{wy \mid w,y∈(a,b)^*\}$ $L_3 = \{zwz \mid w∈(a,b)^*,z∈\{a\}\}$ $L_4 = \{wxw \mid w∈(a,b)^*,x∈\{c\}^*\}$ Find the ...
1
vote
1answer
14 views

An algorithm to decide if a context-free language like $L_1$ and a regular language like $L_2$ have common members

A context-free language (CFL) is a language generated by some context-free grammar (CFG). A regular language (also called a rational language) is a formal language that can be expressed using a ...
1
vote
1answer
23 views

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
0
votes
2answers
22 views

A regular expression that defines a language

I am reading a chapter about regular expressions and there is the following example present in the book : Let $\sum =\left \{ 0,1 \right \}$. Find regular expressions over $\sum$ that define the ...
1
vote
1answer
38 views

Although proven by pumping lemma language is not regular [closed]

We have to show, that although the language $L=\left\{qw^jq^k \mid j,k \in \mathbb N, j>k \mbox{ or }j \mbox{ is not even }\right\}$ satisfies pumping lemma, it is not regular. Okay, my try: For $...
0
votes
3answers
32 views

DFA - Union operation: How to?

I'm currently looking at deterministic finite automata, and learning how to combine two DFAs using AND or OR. I think I understand how to construct the INTERSECTION (AND) of two DFAs, but I'm at a ...
0
votes
1answer
28 views

proving not regular with pumping lemma

Not quite sure if I understand pumping lemma correctly. so if i have this language and i like to show it is not regular: L={ $q^a w^be^c| a,b,c \in N, a+b=c$}. If L would be regular, than there ...
0
votes
2answers
24 views

Constructing DFA - Criteria / Multiple solutions

I'm currently studying for my logic exam, and looking into examples on DFA construction. Assume the alphabet is {a, b}, and the language to be constructed is defined as follows: ...
3
votes
1answer
178 views

Question about regular languages

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?
1
vote
2answers
24 views

Merging of two DFAs

I have 3 languages L1, L2 and L3 with x$\in$L1, y$\in$L2, z$\in$L3 ; x=$a_{1}a_{2}a_{3}...a_{n}$, y=$b_{1}b_{2}b_{3}...b_{n}$ and c=$a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}...a_{n}b_{n}$. Words of L3 are ...
2
votes
2answers
49 views

Proving that a certain language is regular

Consider two languages $L$ and $\operatorname{minimum}(L) = \{ w \in \Sigma^* \mid w \in L, \text{ but no real prefix of $w$ is in $L$}\}$. I want to prove now, that for every DFA language $L$ , ...
4
votes
2answers
43 views

Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
2
votes
1answer
35 views

Show that $L = \{a^p b^q \mid p, q \in \mathbb{N}^0 \setminus \mathbb{P}\}$ is not regular

Full disclosure: this is a homework question, so I'm only looking for a kick in the right direction. The original question notes that $\{a^p \mid \ p \in \mathbb{P}\}$ is not regular and that the ...
1
vote
1answer
31 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
1
vote
1answer
38 views

Infinite recursive languages and infinite regular languages.

Could the following statement be correct? "Every infinite recursive language has as a subset an infinite regular language."
2
votes
2answers
36 views

NFA to DFA for odd a's and even b's

The regular expression for accepting odd a's and even b's I calculated is: (aa)*a(bb)* and the NFA: ...
5
votes
2answers
49 views

Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
0
votes
1answer
77 views

Pumping Lemma - non regular

Can everyone help me to show that: the language $$L = \{a,b\}^* \setminus \{a^m b^{2m} a^n\mid m,n \ge 0\}$$ is not regular. I don't know what is the meaning for the proof.
0
votes
3answers
44 views

Where did I go wrong creating a Deterministic finite automaton?

My goal was to create a Deterministic finite automaton that handled the regular language (00010 + 1101 + 1010)* and had a parity bit at the end to make sure 0's where even. To clarify what I mean by ...
0
votes
1answer
30 views

Finding a Regular Grammar

so I have to find a regular grammar to generate the following sets: $(1)$ $\{aa, ab, ac\}$ $(2)$ $\{ab^n,ba^n\mid n\ge 0\}$ $(3)$ $\{ab^{2n}\mid n\ge0\}$ I'm wondering if anyone can check my ...
2
votes
1answer
41 views

Difference of a regular language and a context-free language

I know that given the context-free language L and the regular language R, the language L \ R is context free. But what about R \ L ? My attempt is as follows: R \ L = R $\cap$ $\overline{L}$ We ...
0
votes
1answer
24 views

Prove that $even(L)$ is regular

For any string $w$, define $even(w)$ to be the string that results from deleting all the letters that occur in odd positions of $w$. For example, $even(a)=ε$, $even(ab)=b$, $even(acb) = c$, and $...
1
vote
1answer
71 views

Is the language of complex numbers regular?

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ ...
0
votes
1answer
20 views

If $L_1.L_2$ is regular, and $L_1$ is regular, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. Now, Is this true? Assume that $L=L_1.L_2$ is a regular language. Also ...
1
vote
1answer
51 views

Find an LL(2) grammar for the following language

The question asks to find both an LL(1) and an LL(2) grammar for the following language {𝑎^𝑚 𝑏^𝑛 𝑐^𝑚+𝑛 | m,n ϵ N} I have an LL(1) grammar like so ...
0
votes
1answer
15 views

regular languages ,context free grammer.

I know that if a language is regular then it is context free. and i know also that the class of regular languages are closed under intersection. Now, Lets say we have two languages that are not ...
3
votes
2answers
37 views

subsets of non regular language

I know that there are many languages that are context free but not regular like $\{a^n b^n :n>0\}.$ But I want to know if every context free but non-regular language has infinitely many non-regular ...
0
votes
1answer
19 views

A regular expression for the language $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$

A language like $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$ is given. The first question : Is this language regular? The second question : If $L$ is regular, How can we write a regular ...
0
votes
1answer
13 views

Which language L have exactly one equivalence class

Consider the alphabet {a,b}, for which language does the equivalence relation R have exactly one equivalence class? From what i understand about equivalence class, each state is consider a class. So ...
1
vote
1answer
37 views

Finding the language of a finite automaton

Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is $L(A) = (a ...
0
votes
1answer
31 views

How do I describe the following DFA

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n($ w $) denote the number represented by $ w $: ...
0
votes
1answer
27 views

A regular expression for the language $L=\{w:(n_a(w)-n_b(w))mod3=1\}$

Assume a language like $L=\{w:(n_a(w)-n_b(w))mod3=1\}$ is given. How can i find a regular expression for this language using a systematic process? Note : I can easily draw a DFA accepting this ...
0
votes
1answer
17 views

If $L_1 \cup L_2$ is regular and $L_1$ is a finite language, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. So, Assume that we have a regular language like $L=L_1 \cup L_2$ and we ...
1
vote
1answer
55 views

Regular expression of the set of strings of even length

I should try to write a regular expression of the set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. If string has even length, and if we have one $k$; there should be (odd ...
1
vote
1answer
168 views

Regular expressions represents the sets provided

While I am studying formal languages, I see these questions.What are the answers for them? a) The set of strings over {a, b, c} that begin with a, contain exactly two b’s, and end with cc. b) The ...
0
votes
3answers
241 views

The family of regular languages

Is the family of regular languages closed under countable infinite unions? If so prove it, If not give a counterexample.
0
votes
1answer
272 views

Is the family of regular languages closed under the operation of set difference?

Prove that the family of regular languages is closed under the operation of set difference. (I tried coming up with an NFA that will recognize the new language, but I get stuck with defining the ...