# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,558 questions
Filter by
Sorted by
Tagged with
19 views

### Is {wєL1| Ǝv wvєL2} regular if L1 & L2 regular languages?

Will the language {wєL1| Ǝv wvєL2} be regular if L1 & L2 regular languages?
23 views

### Formal languages [closed]

first post, hi everyone, got this question in exam, how many complete Deterministic finite automaton we can get with 2 states, and with n states( considering n big number to get a general formula), Σ =...
16 views

### How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
21 views

### Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}

I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
203 views

### How it's possible decide CNF by having a turing machine that decide SAT?

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
19 views

### Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
29 views

### How do right contexts work in context-sensitive L-Systems?

I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
39 views

### Is the language $L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$ regular or not regular?

I'm trying to understand how to prove a language is regular or not regular, for example this language: $$L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$$ Is this language regular or not? My solution Using ...
64 views

### Proof that the complement of a finite language is always an infinite language

Let's say that we have a language $L$ that is finite. How can I prove that the complement of $L$, i.e., $\bar{L}$, is always an infinite language? Obs.: infinite language in this case means that is ...
34 views

### What does $g \to \lambda$ mean in the L-System for the dragon curve?

I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
25 views

### A turing machine L takes a machine <M> which has to halt at for least n Inputs

I've been wondering about this problem for a while: Say we have L = { <M>, n | M has to halt for at least n Inputs} and multitapes are simulating various inputs bla bla How do I count how many ...
25 views

### Say what language is generated by the context-free grammar

In each case below, say what language (a subset of {a, b}∗) is generated by the context-free grammar with the indicated productions. S→ aSa | bSb | aAb | bAa A → aAa | bAb | a | b | Λ I tried to solve ...
32 views

41 views

### Size of minimal DFA

Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
62 views

### Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language

Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ...
63 views

### Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language

I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
26 views

### complement of concatenate languages equal to complements concatenated?

please help me with this one. (a formal answer would be much appreciated) ∀L1, L2 ⊆ Σ: (L1 · L2)^c = L1^c · L2^c when · represents concatination and ^c the complement language. do not know if ...
23 views

### Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$

Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule ...
57 views

### If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that $$L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$ I thought I could take a DFA which computes ...
40 views

### Difference between Counter-machine and stack machine

I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). My question is counter machine means counter coexist ...
44 views

### Could I apply Rice theorem for both TM's property and language property?

I read that Rice theorem applicable only for language property not for machine property. But today I have read from stack exchange and one site they are applying Rice theorem on machine also. My ...
46 views

32 views

### Prove or disprove: $L^n=M^n\nRightarrow L=M$ where $L$ and $M$ are languages

In a homework assignment, it's asked For any alphabet $\Sigma$; for all languages $L$, $M$ on $\Sigma$ Prove that $\forall n>1$, $L^n=M^n\nRightarrow L=M$ The student and I tried in vain to make ...
64 views

### Can you diagonalize a language out of CSL?

In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
30 views

### Test whether words of less a's than b's or c's but not at the same time is context-free

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so. The closest ...
69 views

### Are programs just "words" of a formal language?

Every formal language is a subset of E*. Let's say this formal language is python. If a program is syntactically correct, then the Python Automata accepts the "word", which is the program. ...
### Given two languages $A,B \subseteq \Sigma^*$, prove that $A/B$ is semi-decidable if both the languages are semi-decidable
I have found two interesting questions regarding the quotient of languages, described as: $A/B=\{w \mid \exists z\in B\land wz\in A\}$ The first one is: Let $A$ and $B$ be regular languages, prove ...