Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

250 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
28 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 ...
0
votes
0answers
38 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
0answers
52 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. ...
0
votes
0answers
37 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 ...
0
votes
0answers
110 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}$ ...
0
votes
0answers
107 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 ...
0
votes
0answers
48 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 ...
0
votes
0answers
75 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
0answers
111 views

ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
0
votes
0answers
30 views

Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
0
votes
0answers
33 views

Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
0
votes
0answers
46 views

Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
0
votes
0answers
51 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
0answers
32 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
0
votes
1answer
136 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
0answers
30 views

Automatic stack

Each context-free language has an automatic stack received by a non-deterministic blank. That is, it will not uphold the following determinism requirement:
0
votes
0answers
67 views

Is language bin(n)bin(2^(k+1) n + 1)^R context-free

I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
0
votes
1answer
62 views

Is the empty string and some words of even length are elements of this set?

$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$. I have my answers, but I need confirmation: Is the empty string $\epsilon \in L$? Yes. Reason: ...
0
votes
0answers
499 views

Converting CFG to GNF problem

I have a big problem with converting GNF example. This is my CFG $ S \to AS\mid BS\mid \lambda\\ A \to aC\mid BCA\mid c\\ B \to AB\mid b\mid \lambda\\ C \to S\mid d $ I simplified the CFG by ...
0
votes
0answers
356 views

closure property on Recursively enumerable language

How to prove that recursive and recursively enumerable language is closed under reversal? Why recursively enumerable language is not closed under set difference? [But intersection of recursive and ...
0
votes
0answers
56 views

Is there a pda with maximum 3 state for every CFL?

This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
0
votes
0answers
87 views

how to write a language for context-free grammar generates the empty string?

How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
0
votes
1answer
77 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
0
votes
0answers
32 views

One-way-function based on Friedberg numberings

A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
0
votes
0answers
80 views

What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
0
votes
0answers
39 views

A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?

I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages: $\emptyset$ $\Sigma^{*}$ I assume for 2, a one-state TM that just ...
0
votes
0answers
22 views

Is the language $L$=$\{<D_1,D_2> | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?

I came up with an algorithm to decide this language, but not sure if it is correct? ...
0
votes
0answers
64 views

Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works? we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
0
votes
0answers
322 views

Constructing a PDA to accept the language {a^i b^j c^k where i,j,k>0 and i<=j<=2k}

Can anybody help me out with this? If I try to compare $a$'s with $b$'s to check if $j\ge i$ then I won't be able to compare the same number of $b$'s with the number of $c$'s that is to check if $j\le ...
0
votes
0answers
85 views

Whether following language is linear or not?

I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$. Now, I wanted to determine whether this language is linear or not. So, I came up with this grammar: $S \rightarrow A\thinspace|\thinspace Sc$ $A \...
0
votes
0answers
49 views

Why do we use CYK algorithm?

Why do we use the CYK algorithm? In my book is written that with CYK algorithm you can faster see if a word is generated by a given Grammer. However I dont get it, because I need like 5 min in order ...
0
votes
0answers
222 views

What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"): 2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, ...
0
votes
0answers
110 views

How to check if a string is accepted by a context-sensitive grammar?

Is there an algorithm to determine membership in context-sensitive grammars?
0
votes
0answers
57 views

Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
0
votes
0answers
67 views

Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language. Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt. Proof. Suppose by ...
0
votes
0answers
195 views

How can I find a language from a given PDA

I have the following PDA: And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
0
votes
0answers
170 views

Difference between grammar productions and derivations

My understanding is that a production is a 'rule' of a grammar which defines how a symbol sequence can be rewritten into another symbol sequence. A derivation on the other hand is the process of ...
0
votes
0answers
36 views

Formal language representation of program

I have numerous records, composed of words. Each word gets translated into vectors, with a variable number of channels, provided that that word exists in a specific lookup dictionary. For n number of ...
0
votes
0answers
103 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...
0
votes
0answers
25 views

Formal Class of Languages Describable by .NET Regular Expressions

This is sort of a computer science question and sort of a programming question. What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well ...
0
votes
0answers
73 views

What is the power of a Turing-machine that cannot write?

What is the power of a Turing-machine that cannot write? So it can still read and go back and forth on the tape, but it cannot write. I am wondering what this would be equivalent to in the ...
0
votes
0answers
34 views

Dependency of operations of languages

I've struggled in the closure properties of the general class of languages because I couldn't use any automata concept and grammars. In specific, I'm interested in dependency of operations. (The ...
0
votes
0answers
24 views

Is there any algorithmic way to decide the equivalence classes in the nerode relation?

Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$ The Nerode relation $R_L$ says $xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$ By looking at the language : I can conclude ...
0
votes
0answers
103 views

Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0
votes
1answer
263 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} ]\}$ ...
0
votes
0answers
135 views

Prove that we can convert any given turing machine to a turing machine with only 3 states?

So in a book that I'm reading it says that we can convert any given Turing machine to a standard turing machine with only 6 states furthermore we can convert any given to a turing machine with only 3 ...
0
votes
0answers
147 views

Simulate deterministic PDA with 1-tape Turing machine?

Is it possible to write a 1-tape Turing machine in order to simulate a deterministic PDA? How would this be done?
0
votes
0answers
94 views

Proving P and NP on problems formulated as languages

To prove that a certain problem is in P we have to give an algorithm that decides or solves it in polynomial time. To prove that a problem is in NP an algorithm must exist so that it can check whether ...
0
votes
0answers
473 views

Closure under swap operator

I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator. Let swap : {a, b}∗ → {a, b}∗...