Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
0answers
11 views

Show that 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 ...
-2
votes
0answers
20 views

Is $\{a^{2n} b^{3n} \mid n≥0\}$ a context-free language?

Is $\{a^{2n} b^{3n} \mid n \ge 0\}$ a context-free language? Also. I need to prove that $\{a^s b^t \mid s=t^2, s,t \ge 0\}$ is non-regular using the pumping lemma, and that $\{a^s b^t \mid s \neq t^2, ...
0
votes
2answers
43 views

Show that {xy : x ∈ {a}*, y ∈ {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 ...
0
votes
2answers
61 views

Proving that a language defined by a regular expression is equivalent to a right linear grammar

After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me. Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
0
votes
1answer
12 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 ...
0
votes
1answer
20 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 ...
1
vote
1answer
41 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 ...
-1
votes
0answers
21 views

TM decidable or undecidable problem?

Question: Explain why the following problems are decidable or undecidable (Using rice's theorem where possible). Does the language accepted by a Turing machine contain an even-length word? Holds a ...
0
votes
1answer
35 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 ...
1
vote
1answer
35 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 ...
22
votes
5answers
2k 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 \...
0
votes
1answer
43 views

Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]

We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
13 views

The Turing Machine in the proof of Time Hierarchy Theorem

In the proof of the Time Hierarchy Theorem, Arora and Barak writes: Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
46
votes
2answers
8k 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 ...
2
votes
1answer
29 views

How can I represent this description in set builder notation?

The language that accepts strings with the number of 0s being congruent with 1%3 and an even number of 1s over the alphabet {0, 1}.
-1
votes
2answers
387 views

Uniqueness of solution in Arden's theorem

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below. My question is: What is the logical reasoning to prove ...
0
votes
1answer
46 views

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase? For example, for the SAT problem, the first question is whether the Boolean ...
2
votes
1answer
49 views

How to determine the finite or infinite number of words in a formal language

Let be: Uppercase letters — non-terminal symbols. Lowercase letters — terminal symbols. Possible cases: The number of words is 0 (infinite substitutions). Examples: $$\{S \rightarrow aS\}, \\ \{S \...
3
votes
2answers
3k views

Do Turing machines have memory registers?

I am working on chapter one of the textbook Computational Complexity: a modern approach by Arora, S., & Barak, B. They begin by defining a turing machine (TM) and then prove equivalence between ...
0
votes
1answer
29 views

Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
3
votes
0answers
56 views

Some guess about concatenation of intersection of languages

I know this is an amateur question but is it true to say that for any three nonempty languages $L_{1},L_{2},L_{3}$ over an alphabet $\Sigma$ we have $L_{1}(L_{2} \cap L_{3}) = L_{1}L_{2} \cap L_{1}L_{...
9
votes
4answers
646 views

If $L_1L_2$ is regular language then is $L_2L_1$ regular too?

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular too? I try to find a way to prove it... I can't assume of course that $L_1,L_2$ ...
1
vote
1answer
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 ...
2
votes
2answers
814 views

What is a final state?

I am studying DFA's, but I've been struggling to find an explanation of what does the final state mean? I know that it is indicated by double circle on the graph, but what does it imply?
1
vote
1answer
32 views

Find a transducer that maps a given deterministic process to another

Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
2
votes
1answer
92 views
0
votes
1answer
66 views

Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
0
votes
1answer
148 views

How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
0
votes
3answers
148 views

Difference between a regular and a non-regular language

Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then: is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM? is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?
3
votes
1answer
60 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 ...
0
votes
2answers
239 views

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?
1
vote
1answer
29 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 ...
0
votes
2answers
749 views

turing machine for the language L ={w#w' where w<w'}

I'm blocked with a question for a long time. L ={X=w#w' where w < w' and w,w' in {0,1}* } So i'm trying to find : 1-a deterministric turing maching for the language L. 2-a non deterministic for ...
2
votes
1answer
200 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
1
vote
1answer
68 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. ...
0
votes
1answer
43 views

Can PDA accept only by final state without finish reading input?

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
1
vote
1answer
37 views

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 ...
0
votes
1answer
520 views

How to define a language for an independent set problem of a graph?

Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\{u,v\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}_{>0}$ where $|I|=k$. How can I define the language $L_{P_{Independent ...
3
votes
1answer
90 views

Regular expression vs rational expression

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$. Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows: $|L| ...
22
votes
3answers
520 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
2
votes
1answer
1k views

How would a Turing Machine recognize n consecutive characters

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
27
votes
3answers
2k views

Which languages do Perl-compatible regular expressions recognize?

As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that ...
-2
votes
3answers
79 views

Context-free grammar for $a^{2n} b^{2n}$

I have just started learning formal languages and here is a question I am facing a little hurdle: Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$. This was what I got at first....
0
votes
1answer
43 views

Language for starting and ending with same symbol

Alphabet = {a,b} should null string be the part of this language? L ={^,a,b,aa,bb,abba ......} I have seen on different sources not including null string. Is null string a part of this language or not?...
0
votes
1answer
47 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
1
vote
2answers
105 views

Prove that $(L^R)^* = (L^*)^R$

Prove that $(L^R)^* = (L^*)^R$ for all languages $L$. My attempt: Suppose $w \in (L^R)^*$. So, $w = w_1\dots w_l$, for some $w_1, \dots , w_l \in L^R$. Since $w^R \in L$, then $w^R = w_l\dots w_1$, ...
1
vote
2answers
52 views

For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ if

For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ in case of: $L_S\in RE$ $L_S\in R$
0
votes
1answer
285 views

Proving decidability of language

Prove or disprove: The following language $L$ is decidable: $\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$ ...
3
votes
1answer
72 views

Context free grammar for strings with more $a$'s than $b$'s

I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$...
6
votes
1answer
837 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 ...

1
2 3 4 5
51