# Questions tagged [regular-languages]

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

1,128 questions
110 views

### How I can find all equivalence classes by Myhill-Nerode?

first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest. The topic is Myhill-Nerode ...
38 views

### Maximum number of words in deterministic finished automata with k-states [closed]

I have exercise: We have a given finished deterministic automata. It has 5 states and is based on the alphabet {a, b, c}. It can create n different words (we assume that n < inf). What maximum ...
38 views

### Prefix/suffix property of language containing only empty word

Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property? The definition says that language has prefix/suffix property requires that there is no code word in the ...
40 views

### operate infinite times over a regular language

Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$. Is it possible to prove $T^∞(L)$ is regular? $T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$...
69 views

### Density of regular language containing all squares

I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated. Suppose we ...
45 views

### How can I find the Myhill-Nerode classes for the language A?

I have the following task (no homework). Find all equivalence classes of the Myhill-Nerode relation of the language $$\mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,.$$...
15 views

### Infinite sequence has $m$ consecutive digits – regular languages

Suppose we have an infinite sequence over the decimal alphabet, call it $w$. For $k\in \{0,1,2,3,4,5,6,7,8,9\}$, let $L_k = \{m\geq 0: \text{$w$contains a run of$mk$'s}\}$ be a language. Here a ...
62 views

### Myhill-Nerode equivalence classes of $\{1^n0^n\}$

I have the following task and its solution. Question Given the language $$A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\},$$ ...
54 views

### Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n

The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
54 views

### How to build a finite automaton for right quotient of a regular language?

Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$. Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$. Let $M$ be a finite ...
45 views

52 views

### If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]

How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
70 views

31 views

### is $0^x1^y$ context-free?

given that L is regular, does the following make a context-free language?: i) $\{0^x1^y \mid 0^{x+y} \in L\}$ ii) $\{0^x1^y \mid 0^{x-y} \in L\}$ since L is regular, i presumed that i) can be put ...
36 views

### Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?

My book states that the language $$L_1 = \{a^nb^n\mid n\geq 1\}$$ is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really ...
42 views

### Can Non-Linear Grammars generate Regular Language?

I stumbled upon the following non-linear grammar $$S \to AB$$ $$A\to aaA\mid \epsilon$$ $$B \to Bb\mid \epsilon$$ and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} ...
22 views

### How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]

I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
123 views

### Regular expression or automata for language with odd number of 0's and odd number of 1's

Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
262 views

### Constructive proof to show the quotient of two regular languages is regular

I have a question regarding the quotient of two regular languages, $R$ and $L$. I saw the answers to this question: are regular languages closed under division and the proof sketch is not ...