Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

39
votes
5answers
8k views

How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is ...
26
votes
5answers
12k 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 ...
24
votes
4answers
14k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
24
votes
1answer
4k views

Language theoretic comparison of LL and LR grammars

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
24
votes
2answers
527 views

Determining capabilities of a min-heap (or other exotic) state machines

See the end of this post for some clarification on the definition(s) of min-heap automata. One can imagine using a variety of data structures for storing information for use by state machines. For ...
23
votes
9answers
1k views

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
22
votes
0answers
436 views

Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
20
votes
2answers
543 views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
20
votes
2answers
1k views

Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free

I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question? Anyway, ...
20
votes
3answers
796 views

Is this strange language context free?

Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $ ? I think that it's not context free but I'm having a hard time proving ...
18
votes
1answer
1k views

Are there inherently ambiguous and deterministic context-free languages?

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language ...
16
votes
1answer
295 views

“Dense” regular expressions generate $\Sigma^*$?

Here's a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup ...
15
votes
3answers
225 views

Is this language defined using twin primes regular?

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the ...
15
votes
3answers
642 views

What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
15
votes
4answers
387 views

Are there other ways to describe formal languages other than grammars?

I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
15
votes
1answer
150 views

Is there any nongeneral CFG parsing algorithm that recognises EPAL?

EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar: $S \rightarrow a a$ $S \rightarrow b b$ $S \rightarrow a S ...
15
votes
0answers
316 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
14
votes
5answers
7k views

How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
13
votes
2answers
273 views

Is there a “natural” undecidable language?

Is there any "natural" language which is undecidable? by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
13
votes
4answers
500 views

Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
12
votes
1answer
440 views

What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
12
votes
2answers
424 views

Number of words of a given length in a regular language

Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language $L$ there exist ...
11
votes
2answers
305 views

Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
11
votes
2answers
132 views

Languages accepted by modified versions of finite automata

A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide ...
10
votes
4answers
500 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 ...
10
votes
3answers
393 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
10
votes
2answers
861 views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
10
votes
3answers
621 views

Easy proof for context-free languages being closed under cyclic shift

The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
10
votes
3answers
655 views

How to convert an NFA with overlapping cycles into a regular expression?

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...
10
votes
2answers
628 views

Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...
10
votes
1answer
275 views

Are context-free languages in $a^*b^*$ closed under complement?

The context-free languages are not closed under complement, we know that. As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
10
votes
1answer
172 views

How do I find the shortest representation for a subset of a powerset?

I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness. Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence ...
10
votes
1answer
721 views

Computational power of deterministic versus nondeterministic min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
9
votes
3answers
658 views

Why use languages in Complexity theory

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model. I have a pretty basic question, but ...
9
votes
2answers
514 views

Closure against right quotient with a fixed language

I'd really love your help with the following: For any fixed $L_2$ I need to decide whether there is closure under the following operators: $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$ ...
9
votes
1answer
211 views

Are regular languages closed under sort?

Assume $L$ is a regular language over an ordered alphabet. Is the language built by taking every word in $L$ and sorting it always a regular language?
9
votes
1answer
207 views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in ...
9
votes
2answers
546 views

Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
9
votes
1answer
186 views

Parsing arbitrary context-free grammars, mostly short snippets

I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, ...
9
votes
1answer
752 views

Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties. I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a ...
9
votes
1answer
120 views

How fast can we decide whether a given DFA is minimal?

Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem: Given a DFA ...
9
votes
1answer
384 views

Proving closure under reversal of languages accepted by min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
9
votes
1answer
247 views

Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
9
votes
0answers
118 views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in ...
9
votes
1answer
78 views

Is this language Context-Free? [duplicate]

Possible Duplicate: Is this language Context-Free? The language is defined by $$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$ is Context-Free Language? I believe that the answer is that it is not ...
8
votes
5answers
507 views

A sufficient and necessary condition about regularity of a language

Which of the following statements is correct? sufficient and necessary conditions about regularity of a language exist but not discovered yet. There's no sufficient and necessary ...
8
votes
1answer
659 views

Is an infinite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $; ...
8
votes
1answer
528 views

How to prove regular languages are closed under left quotient?

L is a regular language over the alphabet $\sum = \{a,b\}$. The left quotient of L regarding $w \in \sum^*$ is the language $$w^{-1} L := \{v: wv \in L\}$$ How can I prove that $w^{-1}$ L is ...
8
votes
3answers
537 views

What are the possible sets of word lengths in a regular language?

Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$ Which sets of integers can be the length set of a regular ...
8
votes
2answers
929 views

How can I prove this language is not context-free?

I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a ...