Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
89 views

How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
2
votes
1answer
45 views

Prove the equivalence of regular expressions

I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated. Suppose there exists regular expressions R, S and T. ...
2
votes
1answer
31 views

Show that language of distinct binary strings is irregular

Let $Σ =\{\textbf{[},\textbf{]},\textbf{,},\textbf{0},\textbf{1}\}$, and let $L⊂Σ^*$ be the language containing list representations of finite sets of binary strings: i.e., every string $x∈L$ is of ...
1
vote
0answers
35 views

Prove the ternary representation of there natural numbers is not a regular language [duplicate]

Choose some set in the natural numbers such that the language formed by the set under binary representation is a regular language, but is not regular under any other language formed by some base. ...
1
vote
1answer
37 views

Is there any base representation that produces a non-regular language for set S?

To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc. Given the set $S$ of natural numbers such that $S = \{2^i| i \in \mathbb{N}\}$ prove that ...
-1
votes
0answers
24 views

Show that this language L' is regular [duplicate]

I'm not even sure where to begin with this. The language given is: L' = { x∈Σ* | ∃y∈Σ*, |x|=|y| and xy ∈ L}. Basically, L' consists of the first halves of the strings in L, where L is a regular ...
7
votes
3answers
3k views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let $L$ be ...
0
votes
0answers
25 views

Prove that any PDA/CF language with 1 character is regular [duplicate]

I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
0
votes
0answers
28 views

Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]

I am able to form the regular expression but I am not confident with the grammar. I have tried the following: S-->aaaS|bS|b|lambda Regular expression is given by: ...
2
votes
1answer
48 views

Regular expression for language that does not accept x string (3 letters, |x|=3)

The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
2
votes
1answer
71 views

Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
3
votes
2answers
136 views

Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

I have created the following solution but its left recursive: S--> a|bSc|cSb|Sbc Also it is not accepting: "ab" or "cba" or "abb" or abc. Somebody please guide me. Zulfi.
-1
votes
0answers
16 views

Regular expression required [duplicate]

Give a regular expression for L={a^n b^m |n>=1,m>=1,nm>=3} I tried something like this: a(a)* . bbb(b)*
0
votes
1answer
44 views

Statements about homomorphisms

Consider the following expressions about homomorphisms and show if the statements are true or not. Σ={0,1}, L1 and L2 are Languages ⊆ Σ*, and ᵠ is a homomorphism ᵠ: Σ* → Σ*. ᵠ(L1 ∪ L2) = ᵠ(L1) ∪ ᵠ(...
2
votes
3answers
66 views

How to prove that this language is not regular?

Given a language $L$ over the alphabet { 0, 1, [, ,, <...
0
votes
0answers
21 views

What exactly is “pattern matching”?

I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions. But is there a precise definition? In particular, it seems that it has to do with ...
1
vote
1answer
24 views

Given a regular language, calculate its equivalence classes

I was given the following regular language: For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character from the end is 1. I know it's regular because it can be ...
0
votes
1answer
56 views

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
3
votes
3answers
139 views

Is it possible that the subtraction between two undecidable languages is regular?

If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set? What's ...
0
votes
1answer
25 views

Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
1
vote
1answer
61 views

Prove that $\texttt{prefix}(L)$ is regular

Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular. So far I have provided that the grammar to produce this language ...
0
votes
0answers
27 views

What is a Regular BNF Grammar and a Regular Expression for (simple) Resource Identifiers?

I was trying to make a regular grammar for resource identifier described as follows: Consider the set of all strings over the alphabet $\{ a, b, / , . \}$ that represent an RI (resource ...
-2
votes
2answers
62 views

$L_1 ∩ L_2$ is not regular while $L_1$ is regular and $L_2$ is not regular language

Could you give me an example of languages $L_1$ (regular) and $L_2$ (not regular) where $L_1 \cap L_2$ is not regular?
5
votes
3answers
877 views

How to determine minimum word length of regular language

Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$? A straightforward example: Let's ...
0
votes
1answer
40 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
2
votes
1answer
138 views

Example of non-regular context free language L such that prefix(L) is regular

Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L. What can be an example of non-regular language L such that language of it's ...
4
votes
1answer
37 views

Is unification over regular expression equations doable?

By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations. Generalizing ...
0
votes
1answer
52 views

Every regular language has a finite index

For a language $L$ over an alphabet $\Sigma$, we say that two words $v,w \in \Sigma^*$ are equivalent, denoted $v\sim w$, if for every word $z \in \Sigma^*$, $vz \in L$ iff $wz \in L$. We define $[w]...
0
votes
1answer
26 views

Regular expression for containing 010 as a subword

I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand. I managed to solve the following question: ...
0
votes
1answer
41 views

Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
1
vote
2answers
42 views

Pumping Lemma with Prime Number [closed]

$\text {Could someone please help me with this proof: }$ $L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$ $\text {Maybe we can say, that } w=a^{n}d^{...
1
vote
2answers
68 views

Pumping Lemma on Language with subtracted length

My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given $$ L = \{ a^k b a^{m-...
0
votes
1answer
23 views

Closure of regular languages under “inverse second half”

Theorem. Show that if $L$ is regular, then so is $$ \varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
0
votes
0answers
26 views

Proving that the language of regular expressions is not regular

Prove that the language consisting of all valid regular expressions is not regular. I am approaching this using the Myhill-Nerode Theorem as follows: I am trying to find a pairwise distinguishable ...
22
votes
6answers
11k views

Why is English not a regular language?

Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., ...
4
votes
2answers
2k views

Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
1
vote
1answer
62 views

Can a dfa return only the final state?

I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow: increment x+1 and if x+1 is larger than 15 then x+1 ...
1
vote
1answer
26 views

Prove its not a regular language [duplicate]

I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language. Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language. I can prove it with pumping ...
1
vote
1answer
352 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 ...
77
votes
10answers
110k views

How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
2
votes
2answers
103 views

Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
1
vote
1answer
102 views

Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
3
votes
1answer
100 views

Is Palindrome subset of a regular language regular?

Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*} \mid xx^{R} \in L \}$, then we know that $M$ contains all half copies of palindrome strings ...
0
votes
0answers
28 views

Backwards and forwards automata languages compared with regular languages

Is every language accepted by a BAFDA regular? I am not even sure what the answer is. I tried thinking around canonical examples of non-regular languages (like $0^n1^n$ or $\{ww | w \in \{0,1\}^{*}\}$ ...
2
votes
1answer
27 views

totally ordered semigroups

Given a semigroup is it possible to give a total order to it? If not possible in the general case then what about the case of finitely generated finite semigroups? Does there exist a natural ...
4
votes
2answers
60 views

Finding the number of distinct strings in regular expression

Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
0
votes
0answers
35 views

Regular expression for set of strings with no two consecutive 1's? [duplicate]

I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's. I'm also wondering if there is a pattern that could be extended to ...
2
votes
1answer
253 views

If R is a regular language, is $R^3= R \circ R \circ R$ also regular?

My understanding of a regular language is that for a language to be formal, it must be able to be represented by a DFA or NFA. To prove a language is not regular you can use the pumping lemma to get a ...
3
votes
1answer
112 views

How do I solve these questions regarding homomorphism?

Questions: Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
-1
votes
1answer
46 views

Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...