Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
2answers
77 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 ...
-1
votes
1answer
31 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
24 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 ...
2
votes
2answers
58 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 ...
0
votes
1answer
43 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
47 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 ...
0
votes
1answer
48 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
20 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 ...
2
votes
1answer
31 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}.
0
votes
1answer
58 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 ...
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 ...
2
votes
1answer
53 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
0answers
58 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_{...
1
vote
1answer
33 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 ...
4
votes
1answer
66 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 ...
1
vote
1answer
31 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 ...
1
vote
1answer
73 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. ...
1
vote
1answer
46 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 ...
1
vote
1answer
35 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, ...
0
votes
1answer
48 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?...
3
votes
1answer
105 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}\}$...
0
votes
2answers
62 views

How to define a formal language for describing procedural activities

I do not have a formal computer science background here so I am looking for pointers. How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing ...
0
votes
0answers
53 views

Is $L$ Deterministic Context-Free Language?

Suppose $$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n \text{ or} |w|=n\}$$ Can we conclude that $L$ is DCFl? I think it's DCFL because $$L=\{a^no^n\}\cup \{\{a,b\}^no^n\}$$ Since $$\{a^no^n\}\subseteq \{\{a,...
1
vote
2answers
222 views

Is the following language a Deterministic Context-Free Language?

I tried to show the following language is DCFL (Deterministic Context-Free Language): $$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n_b(w)=n, |w|=2n\}$$ I tried to show that $L$ has a DPDA (Deterministic Push-...
1
vote
3answers
74 views

A non-CFL over {a,b,c} with a non-CFL complement?

I understand uncountably many such languages exist, and the rational for it is clear to me. I just can't think of one trivial, easy to prove example. For instance, the complement of a^nb^nc^n is CF, ...
0
votes
1answer
73 views

Which of the following languages can be represented by regular expressions?

The set of all words contained in $\{0,1\}^*$ that have an even number of 0’s and an odd number of 1’s. I came to discover that it is possible but not sure how. Can anyone express it in a regular ...
0
votes
0answers
46 views

How to carry out expansion in regular expression problems like ((0*10)*)?

I have been given some problems like: Determine if each of the following strings belongs to the corresponding regular language. i. ‘10100010’ and L((0*10)*). iv. ‘011100101’ and L(01*10*(11*0)*) I ...
4
votes
2answers
2k views

Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?

The language given is $L = \{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$. Is this language regular or not? Since there is no pattern, so it should be non-regular? Kindly help!
0
votes
2answers
121 views

Declarative, interrogative, imperative, and exclamative sentences in computer languages

The following English sentences have different forms (syntax): Declarative: You are my friend. Interrogative: Are you my friend? Imperative: Be my friend! Exclamative: What a good friend you are! ...
1
vote
2answers
58 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$
1
vote
1answer
69 views

What is the formal definition of precedence and associativity in programming language?

The concept of precedence and associativity seems straightforward. The operator precedence is a collection of rules that reflect conventions about which procedures to perform first in order to ...
1
vote
2answers
74 views

prove/disprove regularity of languages

Let $L_1 \in REG$ and $L_2 \notin REG$ prove or disprove: $\forall L_1 ,L_2 \text{ } $ $\text{ }L_1^C \cup L_2\in REG \lor L_2\setminus L_1\in REG$ I think that it may be disproved, but I found it ...
-1
votes
2answers
62 views

Is this grammar well-defined? How do I prove the language generated by it is regular?

I have the following problem statement: Is G well-defined here? I am unsure of this since there's no production rule for $X, Y, Z$, and this confuses me a bit. And secondly, how do I prove $L$ is ...
0
votes
1answer
62 views

Recursive languages

I need to prove if the following languages are recursive: $A_1 \subseteq \{0, . . . , 9\}^∗ $ consists of all finite sequences of $\pi$ without the decimal point. We may thus write $A_1 = \{3,31,314,...
0
votes
1answer
55 views

Is $B=\{a^n b^m \mid n \not= 2m\}$ a context free grammar [duplicate]

I was trying to find a grammar that generates $B=\{a^n b^m \mid n \not= 2m\}$ but I couldn't so I'm not sure that it is a CFG. This is what I did : $$ S\rightarrow X \mid aX \mid a \mid b \mid \...
1
vote
1answer
172 views

Prove that the language generated by the grammar $S \to SxS \mid a$ is inherently ambiguous

With the following grammar: $$S \to SxS \mid a$$ Is L(G) inherently ambiguous? What is the proof? I know how to prove the grammar is ambiguous but I don't know how to prove if the grammar is ...
2
votes
1answer
63 views

Left recursive grammar to right recursive grammar

I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is $$E \to E + T \mid T $$ It's equivalent right recursive grammar will be $$\begin{align}E &\to ...
1
vote
1answer
49 views

Proof of an interesting language being non-context free

Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following: Let $L'$ be the ...
1
vote
2answers
62 views

If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?

I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...
9
votes
2answers
333 views

What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive. So this leads to the question: ...
3
votes
2answers
415 views

If regex describes FSAs, what string formats describe Turing machines?

(Topic summary under the line.) Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
1
vote
1answer
64 views

Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?

The title pretty much explains the question, but still: Is the language $$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$ context-free? I think it isn't and would motivate that suspicion by the following ...
0
votes
1answer
37 views

Poping a symbol on a PDA when Input and Stack are Irrelevant

Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special ...
1
vote
1answer
46 views

Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
-2
votes
3answers
176 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
40 views

Question about reduction Proof

I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable. The proof used following idea: Reduce from the $A_{TM}$ problem ...
1
vote
1answer
37 views

Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
3
votes
1answer
76 views

Closure of context-sensitive languages under inverse language substitution

We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
1
vote
0answers
33 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...

1
2
3 4 5
52