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

learn more… | top users | synonyms

0
votes
0answers
55 views

Automata homomorphism relation

We have the following automata $A$: My task is to find automata $B$ and $C$ such that both of them admit a homomorphism to $A$, but $B$ is not homomorphic to $C$ and vice versa. So far, we know ...
-1
votes
1answer
294 views

Show that $\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$ is not regular

How can I show this?I don't know how to start. Show that the set given below is not regular. $$\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$$
0
votes
1answer
69 views

Converting right-linear grammar to left-linear grammar

I have the following language: $$L := \{b(ab)^n a^m \mid n, m \geq 0\}$$ and have created a right-linear grammar: Grammar $G(b(ab)^n a^m)$ Terminals $a, b$ Non-terminals $S, S_1, ...
1
vote
1answer
21 views

Complement of automata

I know that in order for the complement of the automaton to work, it needs to be deterministic and complete, and if it is not deterministic we can always apply the power set construction, and if is ...
1
vote
1answer
51 views

How to check if a language is regular

I'm currently studying a formal languages & automate module on my course and I have been asked to answer the following question: Which of the languages below are regular? If the language is ...
0
votes
0answers
26 views

Length of symbols in the alphabet of the Oxford English Dictionary.

Consider an alphabet $A$ comprised of singleton symbols, so for example we might have $A=\{a,b,c,...,z\}$ or even $A=\{0,1\}$ among many others. The length of each symbol in these alphabets is one. ...
1
vote
1answer
18 views

Cannot create algorithm for decidable language

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w} Hi. I am creating an algorithm to show above L2 is ...
1
vote
1answer
55 views

Is the empty string always in a finite alphabet?

Is the empty string always an element of an aribitrary finite alphabet? I understand that the empty string is part of the Kleene-Star of any alphabet, but is it intrinsically part of any finite ...
0
votes
2answers
35 views

Finite automata problem

I need to draw a finite automata over the alphabet $\{a,b,c\}$, such that the following properties hold: a word starts with at most two $a$ a $c$ is always followed by an even number of $b$ (0 ...
4
votes
1answer
32 views

Identify recursive languages?

Consider the following languages. $L_1 = \{<M> \mid M \text{ takes at least 2016 steps on some input}\}$, $L_2 = \{<M> \mid M \text{ takes at least 2016 steps on all inputs}\}$ and ...
0
votes
1answer
18 views

What is flaw on my proof to identify any string of $L_2$ using single stack?

Consider the following languages: $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ $L_2=\{a^nb^nc^{2n}:n≥1\}$ Which one of the following is TRUE? Both $L_1$ and $L_2$ are context-free. $L_1$ is context-free while ...
1
vote
1answer
26 views

Does $gcd(p,q)$ a period in string, where $p$ and $q$ are periods?

Consider the string $s = a_{1}..a_{n}$. Let's say that $p$ is a period when $a_{i} = a_{i + p}$ for all $i \in [1..n-p]$ Suppose there are two periods : $q$ and $p$, such that $q + p \le n$ then ...
1
vote
1answer
49 views

NFA accepting binary strings mod 5

Could you tell my if my solution is correct? I need to create a NFA which accepts binary strings (reading from right to left) if they are divisible by 5. My automata is below (green vertex is ...
0
votes
0answers
112 views

if in a transition graph there is a walk labeled w, there must be some walk labeled w of length no more than $\alpha+(1+\alpha)|w|$

Generalized transition graph (GTG) is a collection of three things: 1. A finite set of states, of which at least one is a start state and some (maybe none) are final states. 2. An alphabet ∑ of input ...
0
votes
1answer
19 views

Prove that $\delta^*(q,wv)=\delta^*(\delta^*(q,w),v)$

Imagine we have a language like $L$ with alphabet $\Sigma$ and the set of words of $L$ called $\Sigma^*$ ( notice that a word can have zero characters). We define $\delta^*$ recursively like this : ...
0
votes
1answer
25 views

How can we design this one? [closed]

Design a DFA to recognize string over Σ = {0,1} that contains AT LEAST two zeros at its last three positions.
0
votes
1answer
29 views

Up-to-date or Behind - [Markov Chain]

Alex is taking a bioinformatics class and in each week he can be either up-to-date or he may have fallen behind. If he is up-to-date in a given week, the probability that he will be up-to-date (or ...
0
votes
2answers
18 views

What is the automaton recognising the language generated by G?

Why is B not accepted as an answer?: S --> 0A A --> 0A A --> 1B B --> 1B B --> e Which ends up in the state of the automata is in the accept state.
1
vote
1answer
60 views

Regular expression for strings with even number of 1's and number of 0's divisible by 5

I am able to write a DFA for this language but don't see any good way to convert this into a regular expression. This is the DFA I came up with:
1
vote
1answer
20 views

What is the Right Context of a Word in Formal Langauge Theory?

I am reading this paper and am unable to understand this notation in section 2.2 - The right context of a word $u$ according to a language $W$ is the language {$u^{-1}w$ | $w \in W$}. The ...
1
vote
1answer
22 views

Even String of b's Regular Expression

I was able to find a regular expression over the language {a,b} for all strings containing an even number of b's: $$a^{*}(ba^{*}ba^{*})^{*}$$ However I have two questions pertaining to this regular ...
0
votes
2answers
34 views

Is there a language like L in which $\overline {L^*} = \overline L^*$?

Assume that for every language L over the alphabet $\Sigma$, we define $L^*$ , $\overline L$ , $\Sigma^*$ & $L^n$ like this : $L^n$ means joining L to itself n times. For an alphabet like ...
0
votes
1answer
30 views

Constuct DFA from NFA with multiple epsilons

I need to create a Deterministic Finite Automata(DFA) from a Nondeterministic Finite Automata(NFA). I have created the NFA, however i'm having a hard time understanding the steps needed to turn the ...
0
votes
1answer
94 views

Stronger Pumping Lemma for Context Free Languages

Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ...
1
vote
1answer
20 views

Are computable sets closed under XOR?

How do I prove if computable are/are't closed under XOR?
1
vote
1answer
38 views

Proving that reguarity is closed under prefixes?

Show that regularity is closed under prefixes. That is, if $L$ is regular, then so is $$L_1 = \{x \mid \exists y: xy\in L\}$$ I am having a hard time trying to work this through. Can you please ...
1
vote
1answer
26 views

How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$, ...
1
vote
1answer
45 views

Proving that the given language is non regular

We had a question today as follows: Let $L$ be a nonregular language and $X$ a finite set of strings from the same alphabet as $L$. (a) Prove that $L ∪ X$ is nonregular. (b) Prove that $L - X$ is ...
0
votes
1answer
39 views

Identify language of given PDA?

Consider the transition diagram of a PDA given below with input alphabet $Σ =\{a,b\}$ and stack alphabet $Γ = \{X,Z\}. Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA. ...
0
votes
1answer
47 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to ...
1
vote
1answer
24 views

confusion of an example for Powerset construction

I have an example of Powerset construction from the lecture. Powerset construction is applied on automata A1. The result is automata A2. You could see I do Powerset construction myself below the ...
1
vote
1answer
27 views

A proof question involving a regular set and a context free language

Claim: Let $L \subseteq \Sigma^*\{\#\}\Sigma^*$ be a context-free language, where $\# \notin \Sigma$. Suppose that for each $x \in \Sigma^*$, $\{y|x\#y \in L\}$ is finite. Then $\{y|\text{ for some } ...
0
votes
0answers
32 views

Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
0
votes
1answer
19 views

power + operator for binary

What is the specific definition for power $+$ operator in automata theory? For example, when $x$ is a binary what does it mean that $x = 0^+$. Does it mean that x is a string with at least one $0$?
0
votes
2answers
25 views

Reverse of binary number

Let us say that x is a set of binary numbers $$x = \{0, 1, 1001\}$$ Am I correct that $x^R$ is equal $$x^R = \{0,1,1001\}$$ or is it: $$x^R = \{1,0,0110\}$$ What I mean by that is: do we create a ...
0
votes
0answers
14 views

FIRST of a grammar with righthand recursions

$L$ is defined by the grammar $$ S \rightarrow SAB \mid \epsilon \\ A\rightarrow Ba \mid \epsilon \\ B \rightarrow Ab \mid \epsilon $$ What is a $FIRST$ for elements of this grammar? I have two ...
1
vote
1answer
24 views

Parser for reversed language

Language $L$ is specyfied by grammar : $(\{S,A,B\},\{c,d\},S,\{S \rightarrow SA, A \rightarrow Bc | \epsilon, B \rightarrow d\})$. My task is to construct LR(1) parsing table for language $L^R$ ...
1
vote
1answer
31 views

Finite Automata for regular expression

I am trying to construct finite automata for this regular expression: Every block consisting of 5 characters need to contain at least two zeros. The regular expression would look sth like this: ...
3
votes
1answer
79 views

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$? My attempt : Input set is given. So, we have 3 parts of DFA which we can change: Start state Transition Function Final ...
2
votes
1answer
50 views

Is the complement of a given language context-free?

I have a problem with finding out if the complement of language L is context free. $L = \{ ww : w \in \{a,b\}^{*} \wedge \text{ }w \text{ number of }a\text{'s in }w \equiv \text{number of }b\text{'s ...
3
votes
1answer
103 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
0
votes
1answer
45 views

why is the below language a regular set? [closed]

Given a set S={x∣ there is an x-block of 5's in the decimal expansion of π} (Note: x-block is a maximal block of x successive 5's) In the question it is mentioned that there is x-block of ...
0
votes
1answer
15 views

Consider the given regular grammar what are the Myhill-Nerode equivalence classes for the language generated by the grammar?

S → bS | aA | ϵ A → aS | bA A) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #a(w) is odd} B) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #b(w) is odd} C){w ∊ (a + b)* | #a(w) = ...
0
votes
0answers
41 views

Regular and context free language

Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$. It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that ...
-1
votes
2answers
46 views

Automata Theory - Designing a Non-deterministic Finite automata [closed]

I have been combing through youtube looking for a simple explanation on how to "crack" the "NFA" myth. Please help. Since drawing the schematic can be cumbersome, if you can show me how I can derive ...
0
votes
1answer
30 views

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free I am trying to prove it without to build a pushdown automaton First I tried to look which words are in $\mathcal L$, ...
0
votes
0answers
25 views

How many states needed for this FSM, and how do I define them?

I want to define states for FSM that gives an output $1$ if and only if $X$ is dividable by $5$ with a residue of 3. where $X$ is the binary number that the machine got until now (Not Including ...
0
votes
1answer
26 views

how to build a PDA for the language of the intesection of PDA and DFA

lets say we got PDA $M=<Q, \Sigma,\Gamma,\delta,q_0,+,F>$ ('+' marks the end of the stack) with $L_1 = L_f(M)$. and we got $A=<P,\Sigma,\delta_1.p_0.F_1>$ with $L_2 = L(A)$. how can I ...
1
vote
1answer
34 views

Converting an NFA to a DFA

I am trying to convert this NFA to DFA: So I built the power automata, and this is what I got: This should be the answer: I don't understand where am I wrong since ...
1
vote
1answer
30 views

Using Pumping Lemma to prove that $L=\{a^mb^{3m}:m\in\mathbb{N}\}$ is not recognizable over $A=\{a,b\}$

[Pumping Lemma]: Let $\mathcal{A}=(Q,A,\cdot,i,T)$ be a (complete and deterministic) automaton and let $L=L(\mathcal{A})$ be the language recognized by $\mathcal{A}$. If $L$ is infinite and ...