# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,888 questions
Filter by
Sorted by
Tagged with
1 vote
27 views

### Detect (indirect) left-recursion in a context-free grammar?

Given a context-free grammar: A -> α0 | α1 | ... B -> β0 | β1 | ... ... It's straightforward to determine whether the grammar is directly left-recursive - it ...
• 151
37 views

### A term equation

Let $t,a$ are some terms in a first-order language, $x$ is a free variable, the notation $t[x:=a]$ denotes the rezult of replacement in $t$ every occurrence of $x$ with $a$. Suppose, we have a term ...
466 views

### Do all instances of a given string get replaced under a rewrite rule?

I am doing a course in uni on Automata and Formal Languages, and I think I've come across a pretty significant misunderstanding. When you have a rewrite rule in a grammar, and apply it to a string, do ...
48 views

### Is the difference between an unrecognizable language and a finite language decidable? recognizable?

Given 2 languages, A and B, such that A is not turing recognizable, B is finite, is it true that A-B is necessarily not turing recognizable? I am studying to an exam and would appreciate your help! I ...
58 views

### Proving that two languages both represent valid bracket sequences

I have two languages $L_1$ and $L_2$, both subsets of $\{0, 1\}^*$, defined as follows: For $L_1$, we have that $01 \in L$ If $w \in L$, then $0w1 \in L$ If $w_1, w_2 \in L$, then $w_1w_2 \in L$ For ...
101 views

### $LL=\left \{ xyzy^R : xyz\in L \right \}$ is context free language

Let $L$ be a regular language over $\Sigma = \left \{ 0,1 \right \}$. Define $LL=\left \{ xyzy^R : xyz\in L \right \}$ where $x,y,z\in \Sigma^*$. The question asked to show that $LL$ is context free ...
• 189
46 views

### Confusion regarding the conversion of epsilon-NFAs to non-epsilon NFAs

I've begun reading up on NFAs and DFAs, NFAs of both the epsilon and non-epsilon kind My understanding of epsilons are this: They help 'encode' the idea of taking another optional route without ...
• 103
116 views

### Convert a regular expression to a *minimal* LL(1) regular grammar

Given a regular language defined by a regular expression, we can convert it to an NFA, which is equivalent to a right-regular grammar. The grammar is not generally LL(1). However, if we convert the ...
• 151
1 vote
58 views

### Give a class of languages which is closed under intersection and union, but not under complement

I am pondering this question, it is posed early on in a course on Formal languages and Automata, but before much progress has been made on closure of Regular and Context Free languages under ...
28 views

### Proving Non-Semi-Decidability of Language L - Seeking Reduction Strategy

I'm working on a problem involving the language 𝐿 = { 𝑤 ∣ time𝑀𝑤 ( 𝑥 ) ≤ ∣ 𝑥 ∣ + 1 for all words  𝑥 }. The language consists of words 𝑤 where the Turing machine 𝑀𝑤 halts within ∣ 𝑥 ∣ + 1 ...
196 views

### Understanding a bound for derivation length of any string in Pumping lemma for context-free languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz: Let $L$ be an ...
• 137
49 views

### Do all regular languages have a backwards deterministic FSM with one initial state and no $\varepsilon$-transitions?

There's been a question about an algorithm converting an arbitrary FSM into a backwards deterministic automaton without $\varepsilon$-transitions and a single initial state. As commenters pointed out, ...
• 1,549
140 views

### Is there an algorithm to turn any finite automata into a backwards deterministic one, with no $\epsilon$ transitions, and only one initial state?

An automaton is backwards deterministic if, for all states q, p, for all symbols a: $$(\delta(q, a) = \delta(p, a)) \implies p = q$$ (I think the right translation is backwards deterministic, but ...
• 53
43 views

### FSA for 'closure' of a language; how to represent?

Is my interpretation of this correct? I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA. In order to do so, would I draw a new edge from the ...
• 87
1 vote
26 views

### Reachable States in a Product of Transition Systems

I am trying to deepen my understanding of transition systems and synchronization schemes and would appreciate some insights. Consider the following scenario: We have three transition systems A1, A2, ...
• 11
1 vote
59 views

### Splitting strings in pumping lemma for regular language

I was recently reading the book Introduction to the Theory of Computation, Second Edition by Michael Sipser, and encountered the following example: Let $F=\{ww\ |\ w\in \{0, 1\}^*\}$. We show that $F$...
• 13
1 vote
32 views

### Effect of slight modification to LL(1) parse table generation

I am experimenting with LL(1) parsers that do not use a separate lexer. I have the following grammar: S = (('<' S '>' | 'a'+) ' '?)+ The notation uses ' ...
53 views

### Is garbage state necessary in DFA that enforces a particular input combination?

If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex ...
• 87
227 views

### Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?

I am doing a HW problem where I have L1 and L2. I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
• 87
328 views

• 103
37 views

### Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
• 11
52 views

### Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $a(a+b)^*$ to which i applied pumping lemma. Let the pumping length be $'p'$ and the example string be $$w=a(a+b)^{p-1}$$. The string satisfies the condition that it is at ...
51 views

### transforming a grammar from EBNF to LL(2)

I have a grammar in EBNF and want to transform it into an LL(2) grammar. Should I omit A -> empty string ? And is there a scheme I can follow? So far I would ...
49 views

### Does this endomorphism over finite automata have a name?

I found this function that can be applied onto a DFA to produce a DFA. Is there a name for it? Above: A simple DFA over the alphabet $\{0, 1\}$ Below: The resultant DFA over the alphabet $\{0\mathrm{$...
13 views

### Critical Pair Determination in Knuth Bendix

In the Knuth Bendix completion algorithm, how does one identify all the critical pairs for an abstract term rewriting system? Does one have to iterate through each rule, and then identify which pairs ...
74 views

### A specific class of languages

We say a languages $L$ is permutable such that $x\in L$ if and only if a permutation of $x$ be in $L$. Does the set of permutable languages is context-free or not? I think there is a permutable ...
• 1,962
1 vote
56 views

### How to prove a function is a bijection (name mangling)?

I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed. We'...
9 views

### Does a Language Accepted by a Non-deterministic Turing Machine with Zero Errors Necessarily Belong to Class R

It is said that a non-deterministic Turing machine M accepts a language L with m errors if and only if: For every x in language L, M does not accept x in at most m calculation routes. for every x ...
137 views

### Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

Let $L$ be a language over an alphabet $\Sigma$ and let $$\text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \}$$  \text{MAX}(L) = \{ w \in ...
• 213
23 views

### Is complement of this language context-free? [duplicate]

Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language? I know that the class of ...
• 61
32 views

• 21