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

learn more… | top users | synonyms

0
votes
0answers
8 views

How to find transition matrix in cascaded FSMs?

I am considering a 4-state system Equivalently, I can use a cascade approach to represent the same system as In cascade approach, If I consider independent condition on input on both subsystems,...
1
vote
2answers
24 views

NFA without ε-transitions which recognizes the language generated by the regular expression

NFA without ε-transitions which recognises the language generated by the regular expression: 1(0 + 0(10)*0)0 here is what i've done so far..
0
votes
1answer
37 views

Is the problem decidable with Turing machine M that inputs x,y,z does M halts on these 3 instances

Is the following problem is decidable? Given a Turing machine M inputs x,y,z does M halts on these 3 instances? Hint: make y and z any two artificial inputs that the program stops with these inputs. ...
0
votes
0answers
25 views

NFA Correctness

Hello I have the following instructions: L3 is all strings where (i) the number of $b$'s is twice the number of $a$'s, and (ii) each substring with three occurrences of $a$ and $b$ should contain ...
0
votes
1answer
36 views

Deterministic finite automaton parity bit question

for a university assignment ive been tasked with creating a DFA that accepts the regular language (00010 + 1101 + 1010)* and must contain a parity bit at the end to make sure there is an even amount ...
0
votes
1answer
23 views

Problem in Understanding the DFA, Need Help

I am reading Hopcroft Ullman - Automata Theory(2nd Edition). In page Number 65 (Red Underline part in the given Image); I understand when i=1 but unable to understand when i>1 then how the Accepting ...
0
votes
1answer
23 views

Regularity check of languages

L1 will not be CFL also as it needs more than one stack to count. L1/L2 gives concatenation and the result will be $a^{n} b^{2n} c^{4n}$ which is again non regular. Am I right? I am little bit ...
0
votes
1answer
23 views

Prove that $even(L)$ is regular

For any string $w$, define $even(w)$ to be the string that results from deleting all the letters that occur in odd positions of $w$. For example, $even(a)=ε$, $even(ab)=b$, $even(acb) = c$, and $...
0
votes
1answer
49 views

Give a NFA over the alphabet {a ,b , c}

How do I solve this? Give a NFA over the alphabet {a, b, c} whose words have a length which is multiple of 4 or are such that the number of a’a plus the number of b’s in the word is even. Use then ...
1
vote
1answer
70 views

Is the language of complex numbers regular?

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ ...
0
votes
1answer
20 views

If $L_1.L_2$ is regular, and $L_1$ is regular, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. Now, Is this true? Assume that $L=L_1.L_2$ is a regular language. Also ...
0
votes
0answers
15 views

Constructing a grammar for language of all squared words

I need help in constructing a grammar for this language: $L = \{ \alpha \in \{a\}^* \mid \alpha = a^{n^2}, n \in \mathbb{N}_0\}$ All I can tell about $L$ is that it should be at least context-free. ...
1
vote
1answer
47 views

Find an LL(2) grammar for the following language

The question asks to find both an LL(1) and an LL(2) grammar for the following language {𝑎^𝑚 𝑏^𝑛 𝑐^𝑚+𝑛 | m,n ϵ N} I have an LL(1) grammar like so ...
1
vote
1answer
29 views

A grammar for the complement of language $L=\{a^{t+3}b^t:t \ge 0\}$

Assume that the language $L=\{a^{t+3}b^t:t \ge 0\}$ is given. Q1 : How can we write a grammar for the complement of this language? Q2 : Assume that $L'=\{a^nb^m:n\ge0,m\gt n\}$ is given. Can you ...
0
votes
1answer
19 views

A regular expression for the language $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$

A language like $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$ is given. The first question : Is this language regular? The second question : If $L$ is regular, How can we write a regular ...
1
vote
1answer
33 views

Finding the language of a finite automaton

Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is $L(A) = (a ...
0
votes
0answers
15 views

Pupming lemma for CFG in alternative normal form

Let us say that a CFG is given in the following normal form where every production is of either type Non-terminal $\rightarrow$ Non-terminal Non-terminal Non-terminal Non-terminal $\rightarrow$ ...
0
votes
0answers
33 views

Convert a PDA to a CFG

My professor doesn't do a very good job at explaining the process of converting a PDA to a CFG. Can someone help explain it? The way I see it (but it produces wrong results) is each production is ...
0
votes
1answer
31 views

How do I describe the following DFA

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n($ w $) denote the number represented by $ w $: ...
1
vote
0answers
22 views

turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
0
votes
1answer
38 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
0
votes
2answers
28 views

Deterministic vs nondeterministic finite automata

I've just asked a question about non-deterministic finite automata but still feel confused. Here is the attached Deterministic Finite Automata: Deterministic diagram The first node has two ...
0
votes
0answers
31 views

I have a proposal on recursive functions, but I need a second voice to be sure it makes sense.

My main field is computer science. Although I am mostly familiar with computer science theory, I lack in math theory. So, to an average computer scientist, the term ‘recursive function’ will invoke ...
0
votes
1answer
25 views

A regular expression for the language $L=\{w:(n_a(w)-n_b(w))mod3=1\}$

Assume a language like $L=\{w:(n_a(w)-n_b(w))mod3=1\}$ is given. How can i find a regular expression for this language using a systematic process? Note : I can easily draw a DFA accepting this ...
0
votes
2answers
21 views

What ω-language does a Büchi Automaton recognize?

When I'm reading about Büchi Automatons, it says that x is accepted if there are infinitely many occurrences of states from the set of accepting states in the run. But for instance, when I'm being ...
0
votes
2answers
35 views

non-deterministic automaton and regular expression

I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet $\{a,b,c\}$ that accept all and only those strings ...
1
vote
0answers
16 views

Verify correctness of this PDA

I'm trying to construct a PDA for the language $\{a,b\}$ where there are the same number of $a$'s as $b$'s. This is what I have, but I'm skeptical on the correctness. Can anyone verify?
0
votes
0answers
54 views

Turing machine macro notation

This is an example from the book Automata, Computability and Complexity by Elaine Rich. Macro language is defined as follows: (screenshot from the book) And these are the steps mentioned : Scan ...
4
votes
2answers
206 views

Deterministic finite automata (DFA) (have odd length or end with aaa)

Is my attempt is true or where am I wrong? DFA : The set of strings over $\{a, b\} $ that have odd length or end with $aaa$.
1
vote
1answer
160 views

Finite automata NFA

How can I construct finite automata accepting the following language? NFA : The set of strings over $\{a, b\}$ in which every $a$ is followed by $b$ or $ab$. My try
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
303 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
90 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
53 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
29 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
59 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
38 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
21 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
57 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
26 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
68 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 ...