Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

1
vote
0answers
48 views

Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...
2
votes
1answer
81 views

(Transformation) Semigroups, the semigroup $\mathbf D_n$ and the wreath product

I have some trouble understanding the following proof, were I can't even figure out how some terms are defined. But first I state some definitions and preliminary lemmas. A transformation semigroup ...
0
votes
1answer
394 views

Prove that a PDA with accept states accepts all context-free languages

Or in other words that $\forall L: L \in DCFL => L \in CFL$. First of all, does this statement even require a proof? My idea was to let L be an arbitrary language, such that $L \in DCFL$, this ...
0
votes
1answer
58 views

build finite automaton for language minimize states

I want to build a finite automaton that accepts $a^nb^n, n \gt 0, m \ge 0$. I can't do it unless the FA has two final states, i.e.: $delta(q0, a) = q1 delta(q1, a) = q1 delta(q1, b) = q2 delta(q2, ...
1
vote
1answer
319 views

DFA for Boolean Formula

Let $ f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...
4
votes
1answer
408 views

The shortest word in context free language

Let $G=(\Sigma,N,R,S)$ be a context-free grammar. For every production rule A --> w, we say that its length is $r$ if $|w|=r$. In addition $n = |N|$, and $k =$ the maximal length of a production rule ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
1
vote
0answers
118 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
3
votes
1answer
46 views

Irregular $a^nb^n$

We studied in class that regular languages closed under intersection. My question is : if we take the irregular language $L =$ {$a^nb^n : n\geq 0$} and the regular finite language $L' = \{a^3 ...
2
votes
1answer
107 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
2
votes
1answer
83 views

Language concatenation

We learned in class that the regular languages are closed under concatenation (e.g $L_1L_2 =\{ w_1w_2 : w_1 \in L_1,w_2 \in L_2\}$ is a regular language if $L_1$ and $L_2$ are also regular ...
1
vote
2answers
271 views

Proving $L=\{0^n \mid \text{n is a perfect square}\}$ is not a Regular Language without the Pumping Lemma

Is this a valid way of going about proving the proposition? Let $L = \{0^n \mid \text{n is a perfect square}\}$. The regular languages are closed under concatenation. So if $x \in L, y \in L$, then ...
2
votes
1answer
424 views

DFA Rejection State

I'm being asked to construct a DFA for the language over $\{0,1\}$ such that each string of five consecutive symbols contain at least two zeroes. In my construction, it seems to me that it would make ...
0
votes
1answer
22 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
1
vote
1answer
111 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
1
vote
1answer
51 views

Consider this grammar

Consider this grammar: \begin{array}{l} S \to aabBba \mid aAb \mid aab \\ bBb \to bCa \mid aaa\\ aA \to aC \mid bba\\ C \to aab \mid Cb \end{array} This is clearly context-sensitive (CS). It's not ...
0
votes
1answer
64 views

Assign Integer to Each Turing Machine

I have the following problem: suppose that we have an infinite set of symbols, $A = \{a_1, a_2, ...\}$ from which all Turing Machine input alphabets are chosen. Show how we could assign an integer to ...
-1
votes
1answer
184 views

pumping lemma for regular languages and DFA with k states

The Formal statement of the pumping lemma for regular languages: Let $L$ be a regular language. Then there exists an integer $p \ge 1$ depending only on $L$ such that every string $w$ in $L$ of ...
4
votes
1answer
681 views

Routing Automaton

Is there a formal proof for the following question? For a DFA $M= (Q,\Sigma,\delta,s,A)$, we extend the function $\delta : Q \times \Sigma^* \to Q$, such that every $w \in \Sigma^* $, ...
1
vote
1answer
76 views

Infinite regular languages

There is a formal proof for the following sentence? For every 2 languages $A,B$, we write A@B if A subset of B and B\A infinite. Prove that if $A,B$ regular languages and A@b, than exists regular ...
1
vote
1answer
105 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
1
vote
1answer
43 views

Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $

Given $A,B$ regular languages. Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $ Whereas $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite regular language. I ...
2
votes
2answers
49 views

Turing decidable/undecidable

let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$. can you prove whether $X$ is Turing ...
2
votes
0answers
72 views

halting problem

Prove that it is undecidable for the halting problem of a deterministic Turing machine which accepts nonrecursive language or in-other-words: let's say we have a deterministic Turing machine which ...
0
votes
2answers
168 views

What is the language generated by G and how to draw the finite state automaton that recognizes this language?

G = (V, T, S, P) V = (0, 1, A, B, S) T = {0, 1} S is start S -> 0A S -> 1A A -> 0B B -> 1A B -> 1 For the drawing, I am confused about the last ...
2
votes
1answer
51 views

Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
2
votes
0answers
124 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
1answer
114 views

Build regular expression from language

I have the following language: L = {w $\in$ {a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the ...
1
vote
1answer
78 views

One counter automata

A one-counter automaton $M = (Q, S, \Gamma, t, s, A)$ is a pushdown automaton where the stack alphabet $\Gamma$ contains just two symbols $\#$ and $g$. The symbol $\#$ is initially written on the ...
2
votes
0answers
71 views

Turing Machines

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties: $L_1 \cup L_2 \cup L_3 = \Sigma^*$; $L_1 \cap ...
0
votes
2answers
66 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
1
vote
1answer
166 views

unrestricted grammar and Turing machines

Let $G$ be an unrestricted grammar. Then the problem of determining whether or not $L(G) = ∅$ is undecidable. Let $M_1$ and $M_2$ be two arbitrary Turing machines. Show that the problem $L(M_1) ⊆ ...
3
votes
1answer
117 views

reverse automata mininum states

There is a formal proof for the following sentence? For every $k$ there is a DFA (deterministic finite automaton) $M$ with $k+2$ states such that every automaton that accepts the language $L(M)^R$ ...
2
votes
1answer
643 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
0
votes
1answer
122 views

DFA with $k$ states, words of length $k$

Is this statement true? If we have a DFA with $k$ states, and if $L(M) = L$ is infinite, then there is a word of length at least $k$ and at most $2k-1$. Isn't this a trivial answer? Take the ...
0
votes
0answers
36 views

Is this a context-free language?

Let $L = L_1^* \circ L_2^*$ where $L_1 = \{1^n 0^m 1^n : n,m \in \Bbb N\}$ and $L_2 = \{0^m 1^{2m} : m \in N\}$. Is the language $L$ a context free language? I think I can write automata for $L_1$ ...
1
vote
0answers
55 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
0
votes
1answer
49 views

Question about second condition of pumping lemma

I don't think that I fully understand how to use the pumping lemma to prove that a given language is not regular. I'm reading Sipser and according to him the definition of the pumping lemma is: "If A ...
0
votes
0answers
40 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
2
votes
1answer
387 views

Converting CFG to CNF

I have the following problem of converting CFG to CNF: $$ \begin{aligned} S \Rightarrow\,& bA \mid aB\\ A \Rightarrow\,& bAA \mid as \mid a\\ B \Rightarrow\,& BB\mid bs\mid b ...
0
votes
1answer
607 views

Converting NFA to DFA

Im trying to convert a NFA to DFA. This is the NFA and this is the DFA to which i converted Is this right? Also when converting if i write a state as [q0,q1] is this same as [q1,q0] edit: ...
1
vote
1answer
60 views

If $L\cdot\{\epsilon,0\}$ regular language, is $L$ regular?

I've encountered a question during my studies: If $L\cdot\{\epsilon,0\}$ regular language, is $L$ regular? I thought to disprove it by using $A\subseteq 2\mathbb{N}, L=\{w\in\{0\}^*:|w|\notin A\}$ ...
1
vote
1answer
321 views

Proving a set is language generated by given grammar

I have grammar $G$ with productions $S\rightarrow aS|aSbS|\epsilon$, and task is to prove that $L(G)=\{w|$every prefix of $w$ has at least $a$'s as $b$'s$\}$ (I'm not sure if translation is correct, I ...
0
votes
1answer
105 views

Proving Equivalence of DFA and NFA

Im trying to learn Equivalence of DFA and NFA.The problem is that in the below explanation Q' is given as the power set of Q.But this statement seems to be contradictory to the previous statement ...
0
votes
1answer
308 views

Grammar Construction from Given Language!

Just a fast question! I have this language L(G) = { z^n * x^2n with n>=1 } What is the grammar ? I think it should rather be: ...
1
vote
1answer
1k views

Languages and Grammar (Finding a language)

I have a trivial question (that I have actually solved, hopefully) although I am a bit curious if my result is alright. We have $N= \{S , C ,D\}$, $T=\{c, d\}$ and $P = \{S \to Dc, D \to Dd, D \to ...
1
vote
1answer
63 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
0
votes
2answers
48 views

Building an automaton that defines a language

I have $2$ languages, $L_1$ and $L_2$, both are part of $L$-dfa. I have the following language: $$L_0= \{a_1\cdot b_1\cdot a_2\cdot b_2\cdot\ldots a_n\cdot b_n \mid a_i,b_i\in\Sigma, ...
0
votes
1answer
32 views

How is Finite Automation Linked to Lexical Analyser

I understand that Finite Automaton is a Mathematical model of a system with discrete number of input and outputs. Also the system has finite number of states.My question is how is this linked with ...
2
votes
1answer
86 views

Formal proving of languages accepted by a finite automata.

Suppose $L_1 \cup L_2,L_1 \subseteq E^* $ are languages accepted by finite automata and $L_1\cap L_2 =\emptyset $. We need to prove that $L_2 $ is also accepted by a finite automaton. So I've started ...