Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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)}$...
2
votes
1answer
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 ...
0
votes
1answer
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\}\,. $$...
1
vote
1answer
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 $m$ $k$'s}\}$ be a language. Here a ...
2
votes
2answers
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\}, $$ ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
45 views

Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?

Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\...
1
vote
1answer
36 views

How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?

Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular: $$ G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } ...
1
vote
1answer
39 views

How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language? I think this could be a good exercise and the conditions are ...
0
votes
0answers
22 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...
1
vote
1answer
57 views

proof of the rice's theorem

Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given TM’s language has property $P$ is undecidable. Proof:(This is from sipser'...
2
votes
1answer
54 views

How to choose a word to apply the Pumping Lemma?

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :) ...
1
vote
1answer
60 views

Induction on strings (words)

Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word. $quer : \Sigma^*\to \Bbb N$ with: $$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\ ...
2
votes
0answers
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.
1
vote
1answer
70 views

Which word could I use for the pumping lemma?

I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma. Task: Be $\sum { =\left\{ a,b,c \right\} } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \...
2
votes
1answer
79 views

How to prove a language is not regular using the Pumping Lemma?

I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult. Task: Prove that $M = \left\{ a^...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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} ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
5
votes
2answers
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 ...
1
vote
2answers
40 views

Does this DFA describe this regular expression?

For the expression (ab)*ba I came up with the following (very poorly drawn): However, this was not the correct answer - apparently the solution requires five ...
0
votes
1answer
69 views

picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}

If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$ when i pick a word for the language, would it be correct if i pick any of these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^...
2
votes
2answers
58 views

How to prove certain parts of one regular language restricted by another regular language is also regular?

I’ve encountered the following difficult question that I don’t know how to solve. $L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
1
vote
1answer
34 views

Fitting a regular grammar to strings from a PCFG: how big does it get?

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$. For finite $n$, it is always possible to find a regular ...
0
votes
2answers
45 views

What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
0
votes
0answers
28 views

Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]

I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
0
votes
2answers
50 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
3
votes
1answer
107 views

Does every infinite context free language contain an infinite regular subset?

Can someone explain to me if this is true or not?
0
votes
1answer
16 views

Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$

The language was $L =\{a^n b^{n+1} : n\geq0 \}$. This is my attempt: I believed $L$ can also be expressed as: $L =\{a^n b^{n}b : n\geq0 \}$ This implies that the number of $b$'s is always greater ...
4
votes
1answer
53 views

Does the following operation makes the language regular? [duplicate]

I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it. However I thought what could happen if the language is ...
1
vote
1answer
29 views

is it possible to know if a language is regular if its equivalence classes are finite?

i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better. 1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
2
votes
1answer
36 views

Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language

For regular languages $A,B\subseteq\{0,1\}^*$, is $$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$ regular, where $|x|_1$ means the number of appearances of 1 in the word $x$? i need to ...
-1
votes
1answer
38 views

Is it possible to create a regular language from an non regular language? (details inside)

I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it? say L is irregular, if we add or remove finite number of ...
1
vote
1answer
79 views

Does this context-free grammar generate a regular language?

Does the following set of production rules produce a regular language or not? $S \to AB \mid b $ $A \to SB$ $B \to AS \mid a$ I have generated following words with above grammar $b , baa , baaaa , ...
0
votes
1answer
37 views

Can someone explain the language L = {w: w = uu, u \in La(1*01*)}

I need help understanding the language L above. These are my understanding: - w = uu is a concatenation of ...
1
vote
3answers
98 views

Prove a^4n b^m is irregular using puming lemma

My assignment is to prove that the language $L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language. My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an ...
1
vote
1answer
91 views

Proving that co-finite languages can be decided in constant time

I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$. If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$. I'm not sure how to proceed from here. Any hints?
1
vote
1answer
58 views

FSA for $(ab)^*(cb^n)^*$ [closed]

How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$? An automaton can easily be drawn for the part $(ab)^*$, but the part $(...
0
votes
0answers
21 views

Example of a language with linear NFA, but exponential DFA [duplicate]

So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
10
votes
3answers
2k views

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The Problem There is no easy way to get a permutation with a regex. Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters. Regex: Regular ...
0
votes
1answer
29 views

Closure properties between two languages from different grammars

We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular. What if we have a regular grammar that ...
1
vote
2answers
42 views

Show language not regular

How can I show that $\{a^ib^jc^k|i=0 \lor j=k\}$ is not regular? I tried applying the pumping lemma but it does seem to have a pumping length of 1? Alternatively there is the Myhill–Nerode theorem. ...
1
vote
1answer
283 views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...
1
vote
1answer
53 views

Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...