# Tagged Questions

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.

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 ...
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 ...
43 views

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$ ...
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 ...
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 ...
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 ...
30 views

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 ...
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 ...
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: ...
178 views

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?
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 ...
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$ , ...
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 ...
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 ...
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$ ...
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."
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: ...
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 ...
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.
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 ...
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 ...
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 ...
24 views

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$: ...
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 ...
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 ...
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 ...
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 ...