Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
-3
votes
0answers
22 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), Σ =...
0
votes
0answers
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 "...
0
votes
0answers
20 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 ...
0
votes
3answers
201 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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
3answers
60 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 ...
-4
votes
0answers
22 views

How do we prove this NP hard decision problem?

How can we prove this statement? Based on a formal decision problem it can be solved, right, but how exactly we can define this problem to be proved. I am not getting this concept properly. A ∈ P if ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
32 views

$Prove\; that\; L=a^i b^j c^k: i\le j\le k$ i s not context free language

Proof-: Assume L is CFL. Let p is pumping constant for L. w exists in L such that |w|$\ge p$ Let w=$a^p b^p c^p$ |w|$\ge$3p so everything is fine. Now let us see all decompositions of w such that-: vy$...
0
votes
3answers
226 views

Can the diagonal language be empty?

We defined the diagonal language as follows in the lecture: \begin{align*} L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{ ...
0
votes
2answers
41 views

When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?

The question is-: THIS is the transition table for NFA-: Final result as shown in youtube video. https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49 ...
0
votes
0answers
33 views

Show that if $A$ and $B$ are recognizable subsets of $\Sigma^*$ then so is $A \cup B$, $A \cap B$ and also $\Sigma^* - A$

I am working through a chapter of a book by Samuel Eilenberg about Automata, Languages and Machines as part of an university course in computer science. And as an exercise in this chapter I have to ...
0
votes
1answer
23 views

Understanding about pumping lemma for regular language-confusions of beginner-:

I want to understand how is this proof working. What I know-: Pumping lemma for regular language-: Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for ...
-2
votes
0answers
16 views

How to choose splits in pumping lemma to prove language not regular

I am confused how we choose $0\;^{n-p}$ 1 and $0^n$ What's the logic going on here?
0
votes
2answers
46 views

Can a non-recognisable language have a recognisable subset?

If $L\notin$ RE, can there be a language $L'\subseteq L$ such that $L'\in$ RE? Or is it necessarily true that $L'\notin$ RE for all $L'\subseteq L$.
1
vote
1answer
53 views

If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$

I have been given an assignment that I'm having a very hard time understanding. The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (...
1
vote
1answer
43 views

How to write a non-ambiguous grammar for the syntax of lambda calculus?

I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ...
1
vote
1answer
33 views

What does ({a,b}*)² mean?

Pretty much just the title. Is it all possible combinations of a and b that have 2 letters ?
0
votes
1answer
19 views

What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
2
votes
1answer
36 views

Transitions of Turing machine in Cook Levin theorem proof

I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing ...
0
votes
0answers
20 views

Which type of language and machine can parse the following string

Assume that I want to be able to parse strings that follow those rules: ...
1
vote
1answer
40 views

Is language $a^mb^nc^n, m \not= n$ context free

I need to say Is language $a^mb^nc^n, m \not= n$ context free I managed to find a grammar for $L1 = $ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, ...
1
vote
1answer
148 views

A computable language with a non-computable language that is prefix-free

We say that a language $L$ is prefix-free if for every word $s\in L$ there does not exist a nonempty string $w\in\Sigma^*$ such that $sw\in L$ (i.e. no word in the language is a prefix of some other ...
-2
votes
2answers
61 views

Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
1
vote
2answers
42 views

PDA with multiple element access - $i$ - access PDA

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$. Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
2answers
62 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
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
46 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
17 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
30 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
53 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
52 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
57 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
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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. ...
1
vote
1answer
44 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 ...
2
votes
1answer
109 views

Dragon book 4.4.5 exercise?

...

1
2 3 4 5
52