Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0 votes
1 answer
51 views

Is my DFA optimal?

I designed this FSM graph to demonstrate a DFA that would accept any string that is of length 5, must contain a d, can only have as and/or bs before the d, and can only have bs and/or cs after the d. ...
  • 103
-1 votes
0 answers
19 views

Language for the the set of strings with no more than two consecutive a’s [duplicate]

I need to define a basic language for the set of strings with no more than two consecutive $a$’s over $\Sigma = \{a,b\}$. Does this look correct? $L = (\{b\} \cup \{ab\})^* \cup ((\{b\} \cup \{ab\})^* ...
  • 1
0 votes
0 answers
24 views

How to translate Python's For loop into operational semantics?

I've spent hours, struggling to understand the basics of operational semantics. In a couple of resources and videos that I've reviewed, one of the most intuitive example that I found was the ...
  • 1
0 votes
1 answer
66 views

Proof for Language: L1 ∪ L2 ⊆ L1L2

I have a question for my thesis research, but I am not able to find proof of this. Does anyone have any idea on what should be approach be in order to prove this? Question: ...
1 vote
1 answer
28 views

Minimal-length strings which are substrings of no string in a given CFL

Is there an algorithm for enumerating a sequence of minimal-length substrings composed of terminal symbols within some CFG which are not substrings of any string in the language defined by that CFG? ...
  • 113
9 votes
4 answers
1k views

Non-regular language whose prefix language is regular but not the whole set of words

I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...
0 votes
1 answer
38 views

Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?

I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution. My approach was that it has infinite because, lets say we have $x = a^5$ and $y = a^7$. ...
  • 7
-2 votes
0 answers
37 views

All finite languages are regular languages, are all regular languages finite?

my thought pattern here to $L=\{a^* b^*\}$ which is countably infinite, and regular (we can construct a DFA that is accepting) so therefore NOT all regular languages are finite...
0 votes
2 answers
53 views

Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$

i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$ exists $L_1,L_2\subseteq\{0,1\}^*$ with: $L_1$ is $REG$ $L_2$ is $CFL$ and not $REG$ $L_1 \subseteq L_2 $ $L \...
  • 7
0 votes
0 answers
42 views

proof that there exists a regular expression r for every NFA with only 2 states

Let L be a regular language. Then there exists a regular expression r such that L = L(r). Proof for NFAs with only 2 states (can be generalized!), partly seen during a lecture and completed by me: Let ...
  • 89
0 votes
1 answer
60 views

Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?

Lets say the alphabet is Σ=∅,what are the possible languages of this alphabet? According to my definitions: I know that an alphabet is a finite set of symbols Σ I know words is a set of all finite ...
  • 3
0 votes
0 answers
64 views

proof that halting problem is undecidable

In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301, there is a proof for the fact that the halting problem is undecidable. The proof ...
  • 89
1 vote
1 answer
115 views

pumping lemma length restrictions clarification

I know that this kind of question has been asked before, but I still see different kind of answers getting multiple upvotes, but I am not sure if they are all correct. That’s why I wanted to ask it ...
  • 89
0 votes
1 answer
48 views

Is LR(1) closed under union?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 \cup L_2$ also LR(1)? References to proofs would be very helpful.
1 vote
0 answers
31 views

Is LR(1) closed under concatenation?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 L_2$ (their concatenation) guaranteed to also be LR(1)? References to proofs would be very helpful.
-1 votes
1 answer
38 views

Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word

Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word accepts if and only if there are exactly 2 accepted paths and all the others reject or no ...
  • 135
0 votes
2 answers
70 views

Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?

i have seen this question where someone was asking if $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ is context free. Then there was an answer that says that it is context free because: ...
  • 7
0 votes
1 answer
49 views

How to recognize all halting states of a turing machine?

Given a turing machine with some states, how can I recognize all halting states of that machine? I think that I should go over each state and check if there is a transition that is not defined for ...
  • 89
2 votes
1 answer
69 views

minimal DFA transition function clearification

Statement: Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense ...
  • 89
0 votes
1 answer
22 views

Extended transition function in NFA

The following statement seems trivial, but how can it be formally proven/argued? $$\bigcup_{s \in \delta_{N}^{*}\left(q_{0}, w\right)} \delta_{N}^{*}(s, a) \;\equiv\; \delta_{N}^{*}\left(q_{0}, w a\...
  • 89
-1 votes
0 answers
25 views

$L=\{<M>|M$ is a TM that halts on at most one input$\}$ class the L in $R, RE, coRE$

Classify the language if in with class the L in $R, RE,coRE$ and prove your answer $L=\{<M>|M$ is a TM that halts on at most one input$\}$ I think $L\in coRE$, $L$ is similar to the language ...
-2 votes
1 answer
29 views

Is $L=\{\langle M_1,M_2\rangle|L(M_1)\cap L(M_2)\neq \emptyset \}$ R, RE or coRE?

Below is the language, determine (R), (RE), (coRE). and prove your answer. $L=\{\langle M_1,M_2\rangle|M_1,M_2$ are Turing-machines and $L(M_1)\cap L(M_2)\neq \emptyset \}$ Attempt: I Think the ...
  • 1
1 vote
2 answers
47 views

Optimal way to construct union automata of two DFAs

Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the ...
  • 89
0 votes
1 answer
80 views

proving a step in the proof of regular intersection

Let $L_1$ be a context-free language and $L_2$ be a regular language. Then $L_1 \cap L_2$ is context-free. Part of a proof given in the book "Formal languages and automata": Let $M_{1}=\left(...
  • 89
0 votes
0 answers
28 views

Find a context free grammar for $0^n10^m1$, where n is even and m is odd

Let $$L_1 = \{0^n10^m1 | n, m \in N \text{ where n is even and m is odd} \}$$ I tried to build a cfg but I am not sure if it right or if it is the simplest solution. $$ G_1: V = {S}, T = \{0, 1\}$$ ...
0 votes
1 answer
42 views

Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables

For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables. I think that this can be proven ...
  • 89
0 votes
0 answers
27 views

Power of regex extensions [duplicate]

It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
-1 votes
1 answer
40 views

Pumping lemma for context-free languages: Importance of length restriction

(from 'An Introduction to Formal Languages and Automata' by Peter Linz) What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction ...
  • 89
2 votes
1 answer
39 views

What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
0 votes
1 answer
37 views

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
0 votes
0 answers
22 views

What is an example of some production rules which would allow parentheses, curly braces, and square-brackets to be interchangeable?

In computer programming, there are many different ways to write a for-loop. Some examples are shown below: ...
4 votes
1 answer
96 views

Formal grammar of MIU system

The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules: Xi → Xiu mX → mXX XiiiY → XuY XuuY → XY and a start axiom "mi" I have tried to find a formal ...
  • 143
0 votes
0 answers
18 views

Is this Pumping Lemma proof correct? L = {{ca^ndb^m | n >= m >= 1}

Let L be = {ca^ndb^m | n >= m >= 1} Let x be the word = ca^nd^m with |x|= 2n>=n. Look at x = uvw with |V|>=1 and |UV|<=n. We have u= ca^kdb^k, v= b^l, w=b^m-k-l with |v| >= 1 and |uv|...
  • 1
1 vote
1 answer
26 views

prove that there does not exist a Turing machine with a particular property

Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite. The above question ...
0 votes
1 answer
22 views

Transition System vs State Machines

Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (...
1 vote
2 answers
50 views

How to disambiguate CFG with unary/binary minus and binary prefix operator

I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1). I'm facing the current fragment of the language: $$ \begin{...
1 vote
1 answer
62 views

determining whether a context-free language is regular

I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
1 vote
1 answer
27 views

if $RA$ is context-free, is $A$ context-free?

If $RA$ is context-free for a regular language R, is $A$ context-free? I think this statement is true. Let G be the CFG given by the rules $S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, ...
0 votes
0 answers
39 views

How to prove reverse of DFA?

How does one formally prove that, given a DFA $M=\langle Q,T,\delta,q_0,F\rangle$, the following NFA $M^R = \langle Q_R, T, \delta_R, q_R, F_R\rangle$ recognizes the reverse of M's language? We build $...
  • 99
0 votes
1 answer
30 views

prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set

Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set. If $A$ is not the empty set, there should be a way to ...
1 vote
1 answer
34 views

What complexity class is this?

Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question. Disclaimer 2: All corrections to this question are ...
1 vote
1 answer
53 views

Prove a subset of a regular language is regular, context-free but not regular or not context free

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
0 votes
0 answers
57 views

show that neither $S$ nor $\overline{S}$ is turing recognizable

Let $S = \{\langle M\rangle | M \text{ is a TM and } L(M) = \{ \langle M\rangle\}\}$. Prove that neither $S$ nor $\overline{S}$ is Turing-recognizable. I think the statement can be proved via a ...
0 votes
1 answer
69 views

Prove that the language of all Turing machines that accept finitely many words is decidable or not

Question: we have the following language: $$A = \{\langle M \rangle :| L( M)| < \infty \text{ and } M\text{ is a Turing machine}\}$$ where $\langle M\rangle$ is the encoding of $M$ and $L(M)$ is ...
1 vote
1 answer
29 views

Nonexistance of collection of 'transformers' that 'trivially modify' Turing machines?

For a given recursive language $L$, let $TL$ be the language of turing machines that accept $L$, for some encoding of turing machines. $TL$ is countably infinite. Does there exist a set $S = \{S_1,S_2,...
0 votes
0 answers
35 views

Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?

When you are deriving a string using a context-free grammar (CFG), you start with the start symbol and at the right side you have combinations of variables (non-terminals) and terminal symbols. Let's ...
  • 345
2 votes
1 answer
123 views

Formal language rewrite rules: strange notation

I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with. Here is how "Program=Proof" defines a formal ...
1 vote
1 answer
75 views

How are regular languages not structurally recursive?

This blog posting states that "regular languages aren't structurally recursive" while "That's not the case for context-free grammars" In what sense is the term "structurally ...
1 vote
3 answers
143 views

How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
  • 241
-2 votes
1 answer
47 views

Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?

Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$ Why is $L'$ a regular language? I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
  • 241

1
2 3 4 5
55