Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
1answer
11 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 ...
0
votes
1answer
36 views

Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

This problem is from an exercise sheet so it would be nice if you could guide me to the solution. The problem: For $ k \in \mathbb{N}\setminus\{0\}$ let $$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
-4
votes
0answers
49 views

LL(1) parsing problem

Grammar: X  X < Y | c Z b | X > Y | c Z a Y  q |  | p Z  = | <= | >= | X A: Show that the given grammar is not suitable for LL(1) parsing: B: Now modify the grammar, so that ...
-1
votes
1answer
22 views

Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

This is my attempt at a proof: Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$ $L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
0
votes
1answer
14 views

Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

Given the following language, I am tasked with giving a context-free grammar that generates it. $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$ Would this be correct? $A \rightarrow aaaA$ $B\...
0
votes
1answer
24 views

Create an Finite Deterministic Automata 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 ...
-1
votes
0answers
11 views

What does the number in the brackets represent in parsing techniques, such as LL(1), LR(0), etc.?

I am studying language compilers and grammars, and I can't seem to tell what the numbers represent in the brackets of the different parsing techniques. And as a side question (no need to answer): what ...
0
votes
0answers
18 views

Parsing a context free grammar, Backus Naur question

Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of ...
1
vote
2answers
56 views

Proving some subsets of a regular languages to be regular languages

I have to prove that if a language $L$ is regular then: a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular On this one I think I can ...
2
votes
2answers
40 views

Irregularity of $\{0^x1^y : y \nmid x\}$

The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular. How would one prove this using Pumping Lemma? I thought about it ...
1
vote
1answer
536 views

What does it mean for a grammar to be LR(0)?

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0). For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
2
votes
1answer
53 views

How can I show that this language is context sensitive?

I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
1
vote
0answers
30 views

Kolmogorov-Complexity of strings in decidable languages

I just recently learned about Kolmogorov-Complexity and had an idea for giving an upper bound for strings in a decidable language. Is the following statement true? Say we have a recursive language. ...
2
votes
1answer
52 views

What are the most used statements in programming (ranked)?

I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
1
vote
0answers
52 views

How to prove a statement in regular expression?

I cannot figure out how to go about proving this statement in regular expression. $$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$ Here's what I have ...
0
votes
1answer
29 views

Formal proof of language accepted by a specific CFG

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align} Please provide a formal proof for the following ...
0
votes
1answer
37 views

Proving the language of non-primes is in NP

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question. Show the following language is in ...
0
votes
0answers
14 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
0
votes
0answers
32 views

How did we go from Binary to something like Python?

If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
0
votes
1answer
25 views

If two languages are decidable, can one be mapping reducible to the other?

If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
0
votes
0answers
43 views

When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not

I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. ...
5
votes
4answers
538 views

Is there a formal definition of sub-instances or sub-problems?

A decision problem is denoted as a language $L \subseteq \Sigma^{*}$. For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$. For some ...
0
votes
1answer
31 views

Is this an unambiguous CFG that is not LR(k) for any k?

The grammar is this: $$S \rightarrow a B c $$ $$B \rightarrow b B b $$ $$B \rightarrow \epsilon $$ The LR(1) states that I worked out were these $$(1)$$ $$S \rightarrow .aBc$$ $\\\\$ $$(2)$$ $$S \...
0
votes
0answers
28 views

Check if given safety properties are regular, and if so construct NFAs

Let $\mathit{AP} = \{a, b, c\}$. Consider the following LT properties: Between two neighboring occurrences of $a$, $b$ always holds. Between two neighboring occurrences of $a$, $b$ occurs more often ...
1
vote
0answers
29 views

Name for a function on formulae that does not break the structure of given formula

I have two logics, $L_1$ and $L_2$, and a mapping $f: Formulas_{L1} \rightarrow Formulas_{L2}$, and want to argue that the mapping is "nice", in the sense that it is structure-preserving. ...
0
votes
0answers
38 views

How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
1
vote
1answer
34 views

Characterization about Kleene Closure, when is a language $L=L^*$?

I'm trying to find a characterization of when $L=L^*$. I think I have one, but maybe is trivial, but I don't know if the proof is correct. Claim: $L=L^* \Leftrightarrow L=LL$. Proof: If $L=L^*$ then ...
1
vote
0answers
20 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
3
votes
0answers
73 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
0
votes
1answer
31 views

Is this concatenation ({a} · {b})^2 ≠ a^2 · b^2?

I presumed they were equal, such that both resulted in aabb. However, I'm told they are false and I don't know why. Is it because in the second one, we would ...
4
votes
1answer
290 views

Undecidability of “is this CFG prefix-free?”

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...
0
votes
1answer
16 views

Are these production rules for a formal grammar?

I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states ...
0
votes
2answers
28 views

How to tell if a grammar is LALR(1) formally?

There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations ...
0
votes
2answers
22 views

string concatenation vs language concatenation

What exactly is the difference between $$ C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\} $$ and $$ D = \{a^nba^nba^nb | n \geq 0 \} $$ It is known that D is non-regular and C is regular, but I am not sure ...
0
votes
2answers
63 views

How do Context Sensitive Grammar systems work?

The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
0
votes
1answer
29 views

Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$

Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$ I have tried to find a pushdown automata and it turned out to be a ...
1
vote
1answer
22 views

How to find the language of a CFG from Production rules

I'm having problems in finding language of the CFG from given production rules. For example if the production rules are \begin{align} &S \to AS \mid \epsilon \\ &A \to aa \mid ab \mid ba \mid ...
6
votes
1answer
349 views

What are the closure properties of LL(k) languages?

Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by ...
0
votes
0answers
86 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...
1
vote
1answer
27 views

Proof that languages are Turing-recognizable iff computably-enumerable

A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes. In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
1
vote
2answers
24 views

Can you say anything interesting about a language knowing only that it is prefix-closed?

Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$). Knowing only ...
0
votes
0answers
17 views

Show {𝑎^i𝑏^j𝑐^k, i!=j!=k} is context free or not, how can we prove it? [duplicate]

I stuck on this question for a long time and cannot figure out how to prove it?
0
votes
0answers
25 views

Show {𝑎^i𝑏^j𝑐^k, 𝑖!= j and 𝑗 != 𝑘} is a context-sensitive language, what is the grammar? It is context free or nor?

I've been pondering this question for a long time, that 𝑎^i𝑏^j𝑐^k, 𝑖!=j and 𝑗 != 𝑘 is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such ...
4
votes
1answer
618 views

Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
0
votes
1answer
35 views

Can this language be called regular?

Recently, I was facing some problems in effectively proving the following : Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
0answers
49 views

a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a ...
0
votes
0answers
18 views

Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
0
votes
2answers
82 views

How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular. If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
1
vote
1answer
28 views

Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is ...
0
votes
1answer
37 views

What becomes of context-sensitive grammars if $\epsilon$ productions are allowed?

The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can ...

1
2 3 4 5
48