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

learn more… | top users | synonyms

-2
votes
0answers
28 views

Does a NFA accept context free languages? [closed]

A NFA accepts regular languages (Type-3). So because of the chomsky hierarchy every regular language is also context-free. So a NFA accepts context free languages. Am I wrong? Moreover a NFA accepts ...
0
votes
1answer
49 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
2
votes
2answers
56 views

Language to Construct Finite State Transducer

I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing. You typically ...
-2
votes
1answer
36 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
2
votes
1answer
29 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
-1
votes
3answers
124 views

Problem understanding DFA & NFA equivalence in Theory of Computation

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction but my question is a bit different from that. I was reading Michael Sipser's ...
5
votes
1answer
67 views

Infinite non-regular decompositions of regular languages

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case? Or, from a different ...
0
votes
1answer
37 views

Is there a PDA for every Type 3 Grammar?

we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset ...
3
votes
1answer
125 views

Generators of families of langauges?

From Wikipedia's definition of regular langauges The collection of regular languages over an alphabet $Σ$ is defined recursively as follows: The empty language $Ø$ is a regular language. ...
1
vote
1answer
184 views

Why is this language over {a,b,c} regular?

The language of all words over the alphabet {a,b,c} such that the number of as in the word minus the number of cs in the word is divisible by three. How is this language regular? Lecturer ...
1
vote
1answer
88 views

requirement for pumping lemma in regular language

I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not. This is what I have understood so far though For a regular language $L$, there ...
-1
votes
2answers
137 views

Using the Pumping Lemma to show that the language $a^n b a^n$ is not regular

I've seen a lot couple of questions regarding the pumping lemma that are pretty similar to each other and this one is unfortunately not the exception. Most likely will be this question marked as a ...
1
vote
1answer
122 views

Draw a graph of DFA for a regular language

I'm trying to draw a DFA graph for the regular language where every chain: ...
2
votes
1answer
20 views

Concatenation property of regular languages

If L is the empty set and therefore a regular language, I know that L concatenated with sigma star is equal L; Are there any other languages that, when concatenated with sigma star will result in the ...
0
votes
3answers
110 views

Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
0
votes
1answer
70 views

Build a regular expression to define a regular language [duplicate]

The language is an infinite set of chains that are defined by the next conditions. Conditions: ...
2
votes
3answers
74 views

What is the regular expression to the given language?

I can't really find out, how can the following given Language be written down with regular expressions $ L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \} $ I had some guesses, but I don't know ...
10
votes
1answer
158 views

The number of different regular languages

My question is: Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state nondeterministic finite automaton? As an example, let us ...
1
vote
2answers
120 views

Is $a^n b^m$ never regular if n and m have some relation between them?

I know what regular and context free language are and how regular language needs finite memory and other stuff. What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation ...
-1
votes
1answer
74 views

induction proof for kleene star

i posted this on mathematics stack exchange here before i realised this one existed. i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of ...
4
votes
1answer
79 views

What does $\{$ a set $\}^{+}$ mean in the context of languages?

I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$ What does the + mean, i.e., the plus operator applied to a set?
7
votes
1answer
116 views

Proving a language (ir)regular (standard methods have failed)

I'm currently trying to prove a language regular (for personal amusement). The language is: The language containing all numbers in ternary that have even bit-parity when encoded in binary. Now, I've ...
5
votes
3answers
452 views

Is it compulsory that every infinite set be non regular?

I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing ...
3
votes
1answer
56 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in ...
2
votes
1answer
111 views

Why is TIME(n log (log n)) \ TIME(n) = ∅?

In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be ...
0
votes
1answer
45 views

a regular language so that $unary(L) \notin $Context Free Languages [closed]

I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free. unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$ Example $L = \{0, 11\} $ $\rightarrow ...
1
vote
2answers
36 views

NDFA associated with language L

Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language $L \subseteq \Sigma^*$ $L' = \{y \in \Sigma^*:\exists x\in L. |x| = |y|\}$ $L \subseteq ...
-2
votes
1answer
78 views

Is the language $\{ a^pb^q \mid p, q \text{ are prime} \}$ regular? [closed]

I am interested to know whether that language $$ L = \{ a^pb^q \mid p, q \text{ are prime} \} $$ is regular. How do you prove that it is not regular?
2
votes
1answer
56 views

Proving that the continuation of a non-regular language is not ω-regular

I want to prove that a language is not $\omega$-regular. The language I'm working with can be defined as: $$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$ where ...
3
votes
1answer
80 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
2
votes
0answers
64 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be ...
0
votes
2answers
92 views

Generating all strings that a regular expressions describe

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this: ...
2
votes
1answer
50 views

Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

I was wondering if this language is context-free: $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ I know that this language is not regular because it fails the pumping lemma ...
0
votes
1answer
50 views

If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? [closed]

If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free? I am aware that if $L_1$ and $L_2$ are context free languages then the ...
1
vote
1answer
40 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
0
votes
1answer
54 views

Using the pumping lemma for a proof by contradiction [duplicate]

I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm ...
0
votes
1answer
73 views

Pumping lemma on {a^n | n=3^k} — help finishing the proof [duplicate]

I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great. So I am given this language: $L ...
-3
votes
4answers
60 views

Concatenation of regular languages [closed]

Suppose we have two language L = {0^n|n>=0} M = {1^n|n>=0} We know both of these are regular languages. Will L.M (concatenation) be a regular language? ...
3
votes
1answer
151 views

Regular expression to show that all strings contain each symbol atleast once

I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so ...
2
votes
0answers
115 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
-1
votes
1answer
65 views

Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's. How can I construct a new DFA for the regular language $L1 \cup L2$?
1
vote
0answers
44 views

Proving a language is regular or non-regular [duplicate]

I'm struggling a bit to understand two of the problems we were given in class. Could someone look over my work and maybe give me a few hints? State whether the following languages are regular or not ...
0
votes
2answers
84 views

A flawed theorem about regular languages

I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem: The language ${awwa \mid w \in {a,b}^* }% is regular. Well, that part is ...
2
votes
0answers
40 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
10
votes
4answers
570 views

Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or ...
3
votes
1answer
177 views

Kleene star of an infinite unary language always yields a regular language

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$. Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be ...
-1
votes
2answers
113 views

Prove that languages which contain words whose lengths are multiples of a constant are regular

This is a problem involving the theory of regular languages. I am stuck on this problem and do not know how to solve this type of problem. Prove that the language $B_n = \{ a^k \mid k \text{ is ...
-1
votes
1answer
77 views

Left Linear Grammar: How to construct?

I need help constructing a Left Linear grammar for the language $L = \{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \}$ Here is what I have so far, I know : $N = \{S\}$ $T = \{ a, b, c \}$ $P = ...
3
votes
2answers
109 views

Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the ...
5
votes
2answers
76 views

Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...