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

learn more… | top users | synonyms

0
votes
0answers
22 views

How to derive Turing Machine language?

Say you're given a TM (Turing Machine) $M = (Q, \Sigma, \Gamma, \vdash, \sqcup, \Diamond)$ and given the partial $\delta$: $$\begin{array}{c|cc} ...
1
vote
0answers
14 views

How to make the NDPA of this question?

Say $w^R $ is the reverse of $w$. E.g.: $\epsilon^R = \epsilon$ and $(abbab)^R = babba$ Now say $L = \{ww^R | w \in L (a^*b^*)\}$ Draw the NDPA $M$ with $L(M) = M$ I understand NDPA's, however I ...
1
vote
2answers
28 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
4
votes
2answers
39 views

Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
0
votes
1answer
25 views

Prove that there exists an equivalent grammar in Chomsky Normal Form like $G'$ such that $G'$ has at most $(K-1)|P|+|T|$ production rules

A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components: a set of terminal symbols, which ...
2
votes
1answer
32 views

Accurate model of a laptop when it is not connected to any external device

You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your ...
2
votes
1answer
31 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
1
vote
1answer
27 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
0
votes
0answers
17 views

How to decompose a Finite State Machine (FSM) into a cascade of two or more FSMs?

I am coming from Electrical Engineering background and would like to know how can I decompose a given FSM into a cascade of two or more FSMs. To be more precise, I am looking at following questions ...
0
votes
0answers
27 views

is this grammar ambiguous? and what is the recursive inference, the leftmost derivation and the parse tree for the word abcddd?

first question is, is this grammar ambiguous? how can i show that is there a way? and second question is what is the recursive inference, the leftmost derivation and the parse tree for the word ...
0
votes
1answer
31 views

Give a context-free grammar that generates the language

Give a context-free grammar that generates the language: $\{a^i b^j c^k d^h \mid i, j, h \geq 0, k>0 \text{ and } i+j \leq h\}$ This is what I've done so far: $S \rightarrow aSb \mid bSc \mid ...
0
votes
0answers
14 views

generating transition diagram and accepted language from prime number expression

I have the following expression and have to generate the diagram $(M(5))$ and accepted language $(M(5))$ for it, the issue is that I am having trouble even understanding what the expression is saying. ...
1
vote
0answers
32 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
0
votes
0answers
19 views

What is an automata network?

I've tried Wikipedia and Google as first steps, but while I've found some interesting papers and articles, and a couple expensive textbooks, I've yet to find a clear definition of an automata network ...
-1
votes
0answers
70 views

Find $A^n$ for n=0,1, and 3: Languages and FSM

I am having trouble trying to work out this finite state machine and languages question. Let $A=\{11,00\}$. Find $A^n$ for $n=0,1, 3$. Where would I begin?
0
votes
1answer
50 views

What's the meaning this DOT notation?

I'm reading a chapter in a Model Checking book. I came across this chapter "Symbolic Model Checking", in which the author mentions Fixed Point representation. I don't know how to explain the context, ...
5
votes
2answers
42 views

Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
0
votes
1answer
17 views

accepted language notation for CFG for recurring 1's and 0's

Hi I often have trouble with the notation when having to write the accepted language for a finite automata or CFG. Right know I have a CFG that generates groups of any number of 1's followed by any ...
0
votes
0answers
7 views

What is the instruction for the following PDA?

I don't understand why there is a push(a,X,a) but then there is no pop - a instruction.
1
vote
2answers
25 views

Give a regular expression

Let Σ be {0, 1} Give a regular expression generating words over Σ containing an even number of 1’s or with a length which is multiple of 3. i came up with this solution: ε ( ((0*(10*10*)) + ((0+1) ...
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 ...
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
36 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
24 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
35 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
22 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
48 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
67 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
18 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
14 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
46 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
30 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
28 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
36 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
25 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
30 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
48 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
158 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