1
vote
1answer
48 views

Non Deterministic PDA accepted language not clear

This is a PDA from the lecture slides I'm using: They say it accepts all words that contain double a's. While it makes some sense it's not full proof. What prevents the second a to be read in the ...
-2
votes
0answers
28 views

Does a NFA accept context free languages? [closed]

A NFA accepts regular languages (Type-3). So because of the chomsky hierarchy every regular language is also context-free. So a NFA accepts context free languages. Am I wrong? Moreover a NFA accepts ...
4
votes
0answers
64 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
0
votes
1answer
67 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
3
votes
3answers
59 views

generate possible inputs valid for automata

I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not. Can we do the reverse ? I am looking for solution which ...
3
votes
2answers
93 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
0
votes
2answers
38 views

Can a language be the one recognized by more than one automatons?

The language recognized by an automaton is defined as the set of strings that are accepted by the automaton. I wonder if it is possible that the languages recognized by two automatons are the same? ...
6
votes
1answer
210 views

Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with ...
5
votes
1answer
107 views

Where/when did Stephen Kleene first define the Kleene closure/star?

I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure. Is there a paper ...
1
vote
1answer
57 views

Turing machine with repeated strings

How would I go about making a Turing machine to accept the following language L? $$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$ I was thinking counting the number of symbols in the input ...
1
vote
2answers
94 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
5
votes
2answers
58 views

Intersection of two NPDAs

Is there a way to take the interection of two NPDAs? I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
1
vote
1answer
24 views

In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton?

The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical ...
2
votes
3answers
100 views

Language Recognition Devices and Language Generators

I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses ...
2
votes
0answers
115 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
1
vote
1answer
96 views

Can reversing the final and non-final states of a DFA produce the complement of the original language?

Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of ...
5
votes
1answer
91 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
3
votes
1answer
83 views

NFA to DFA final states proof

When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA. What should my arguments be in order to prove this? ...
3
votes
1answer
45 views

If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?
1
vote
1answer
46 views

Finite Automata Input Confusion

I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs. I am wondering what would happen when you have the input string 'abba' with this ...
0
votes
2answers
83 views

Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example: Assume the following regular expression: ...
6
votes
3answers
173 views

Demonstrate that DPDA is closed under complement by construction

I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
3
votes
2answers
119 views

What does the symbol # mean when it comes to languages

Given the following: $$\{ w\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^*$} \}$$ What does $w\#x$ denote?
0
votes
1answer
99 views

Turing machine with possible transitions to the final state [closed]

Let's say we want to draw the transition graph of a Turing Machine that accepts that language L and then write the sequence of moves done by the TM when the input sequence is $w = abbcbba$ so I had ...
0
votes
1answer
498 views

Pushdown automaton for complement of $L = \{ ww \mid w \text{ in } (0,1)^*\}$

I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams). So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not ...
0
votes
1answer
334 views

Can a Turing Machine decide only non-regular languages?

I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \{0,1\}^*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular ...
2
votes
3answers
510 views

Turing machine for $a^i b^j$ with $i \geq j$

I would have a brief question about how to construct a Turing machine that is accepting only this language: $\qquad\displaystyle L_2 = \{a^i b^j \mid i \geq j \}$. I can't come up with any mechanism ...
1
vote
2answers
281 views

Context-free grammar for language with unequal numbers of a and b

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e. $\qquad \displaystyle \{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are ...
3
votes
1answer
116 views

Abstract machine that can recognize repetition

Let $C$ be an infinite set of characters. I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$. For example, if ${x,y,z} \subset ...
0
votes
1answer
49 views

Deciding the class of certain languages [closed]

I am preparing for my exam in Formal languages and Automata theory and I'm looking at some old exam questions right now. I need help with the following question: For each of the following ...
4
votes
2answers
822 views

Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$

I'm having a lot of trouble constructing a PDA for the language: \begin{equation*} \{a^m b^n : m < 2n < 3m \} \end{equation*} I know if I push a symbol for each $a$ I see, then pop 2 symbols ...
1
vote
1answer
70 views

Proving a PDA with CFG Transitions recognizes Context Free Languages

I'm working on a proof that deals with a modified PDA, which is identitical to a PDA, but with transitions: \begin{equation*} a,b \to c \end{equation*} where $a$ is a context free grammar, instead of ...
2
votes
0answers
78 views

Example of execution fragment of multi-process transition system

Here is a simple transition system of beverage vending machine: The exemplary execution fragments can look like this: Now, imagine we have multi-process TS where processes are identical and ...
0
votes
2answers
550 views

DFA/NFA/ε-NFA: subsetting each other or different sets?

I know that an ε-NFA (NFA with epsilon transitions) is not an NFA or a DFA and an NFA is not a DFA. HOWEVER, say you have a complete DFA. Isn't that theoretically an NFA and an ε-NFA? Just because it ...
0
votes
1answer
51 views

Reducing states of a GTG

I used this generalized transition graph with 3 states and got an equivalent generalized transition graph with 2 states: GTG: Equivalent with 2 states: I'm not sure about the regular ...
2
votes
1answer
59 views

Regular Expression as basis for creating this grammar

I made a right-linear grammar from a regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^{*}(ba)^{*}bb$ My solution, it seems a little too short like I'm leaving ...
0
votes
2answers
205 views

Fundamental algorithms in formal language-automata theory [closed]

I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ...
5
votes
3answers
212 views

Bridge theorems for group theory and formal languages

Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines? I am looking for references/applications. However ...
6
votes
1answer
177 views

For what kinds of languages is min |NFA| = Ω(min |DFA|)?

Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that ...
2
votes
1answer
238 views

DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring

In trying to gain a better understanding of finite state machines, I stumbled across this idea and have been confused as to how to approach this case in terms of a DFA. The set of binary strings ...
8
votes
1answer
147 views

What is the complexity of the emptiness problem for 2-way DFAs?

I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape. According to Wikipedia, they are ...
6
votes
2answers
126 views

Push Down Automatons “guess” - what does that mean?

I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
6
votes
3answers
215 views

Algorithm to shrink a DFA by introducing nondeterminism?

This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question. I'm doing research where I'm trying to find the structure of complements of a ...
4
votes
3answers
159 views

Are there algorithms to exactly minimize NFAs which are sometimes efficient?

I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time ...
5
votes
1answer
147 views

Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ ...
7
votes
1answer
152 views

Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?

These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
7
votes
1answer
137 views

Is the universe problem for one-counter automata with restricted alphabet size undecidable?

Consider the following universe problem. The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$. In [1], ...
3
votes
1answer
140 views

What does it mean to say that a language is “effectively closed” under an operation?

I've been reading some formal language theory papers, and I've come across a term that I don't understand. The paper will often refer to a set being "effectively closed under intersection" or other ...
6
votes
2answers
109 views

Classes of NFAs which allow efficient subset testing or unambiguity conversions

I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete. I'm wondering, ...
2
votes
2answers
398 views

Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state

I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question. The question states that the PDA has at most 2 states. Clearly 1 will ...