Stack Exchange Network

Stack Exchange network consists of 174 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 [formal-languages]

Questions related to formal languages, grammars, and automata theory

16
votes
2answers
2k 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. ...
11
votes
2answers
4k 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 context-...
7
votes
3answers
262 views

How can solutions of a Diophantine equation be expressed as a language?

I was given the question Where does the following language fit in the Chomsky hierarchy? Nonnegative solutions $(x,y)$ to the Diophantine equation $3x-y=1$. I understand languages like $L = \...
5
votes
1answer
510 views

Can every linear grammar be converted to Greibach form?

Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$? ($T$ is the set of ...
4
votes
1answer
215 views

Pumping Lemma: is it valid to “multiply the product of powers” in this case?

I need to show that $\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$ is not a regular language using pumping lemma. Can I multiply the product of the powers and express it to: $S = \...
5
votes
4answers
3k views

A DFA for recognizing comments

The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with ...
15
votes
1answer
1k 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: ...
8
votes
1answer
556 views

Proving closure under complementation 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: ...
16
votes
1answer
468 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: ...
18
votes
3answers
324 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 ...
16
votes
2answers
318 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 ...
11
votes
2answers
8k views

Are all context-free and regular languages efficiently decidable?

I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
42
votes
1answer
9k views

Show that { xy ∣ |x| = |y|, x ≠ 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, here'...
3
votes
3answers
1k views

Understanding $\text{handle}$ in parsing problem

Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there The BNF is defined as followed: ...
14
votes
2answers
2k views

Decidable non-context-sensitive languages

It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
87
votes
5answers
56k 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 context-free....
18
votes
3answers
804 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, ...
11
votes
1answer
3k 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 $; i....
21
votes
2answers
893 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 ...
14
votes
3answers
1k 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 language?...
11
votes
5answers
2k 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 ...
23
votes
3answers
2k 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 ...
43
votes
2answers
1k 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 ...
35
votes
2answers
5k 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 ...
22
votes
1answer
253 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 ...
59
votes
1answer
10k 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 ...
32
votes
9answers
3k 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 ...
7
votes
1answer
564 views

How to convert a non-embedding context free grammar to regular grammar?

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any ...
5
votes
3answers
2k views

Closure of Deterministic context-free languages under prefix

For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be: $\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$ ie. ...
13
votes
1answer
3k views

Is there a context free, non-regular language $L$, for which $L^*$ is regular?

I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it?
7
votes
1answer
699 views

Converting a context free grammar to a PDA — is my solution correct?

I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG: $\qquad\begin{align} S &\to R1R1R1 \\ R &\to ...
11
votes
4answers
379 views

Can you specify a programming language without implementation?

Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to ...