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

learn more… | top users | synonyms

2
votes
1answer
47 views

CF grammar on this language

I'm trying to write a context-free grammar for this language: $L = \{a^n b a^m (bb)^n : m \ge 1, n \ge 0\}$ I was getting lost with maintaining $n$ number of $a$'s and $(bb)$'s and I'm not sure how ...
2
votes
2answers
682 views

Lambda productions in grammar

I tried removing the $\lambda$ productions from this grammar: $S \rightarrow a A b \mid B B a$ $A \rightarrow b b \mid \lambda$ $B \rightarrow A A \mid b A a $ It seems like you just take away the ...
0
votes
1answer
38 views

S-grammar for this regular expression

Given this regular expression: $r = a a^* b + b^* c b$ I think this is the simple grammar, but I was getting a little lost with the productions: $S \rightarrow S_1 | S_2$ $S_1 \rightarrow a A b$ ...
1
vote
1answer
219 views

Greibach normal form conversion

I'm trying to convert this into GNF: $S \rightarrow ASaa | bab$ $A \rightarrow Ba | bAB$ $B \rightarrow abba$ So I'm getting this, but I'm not sure understanding and applying correctly the concept ...
0
votes
1answer
192 views

Grammar into Chomsky Normal Form

Convert the following grammar into Chomsky Normal Form (CNF): S → aS | aAA | bB A → aA | λ B → bB | aaB I think this looks ok, but not sure. Maybe someone can point out where I go wrong: ...
1
vote
1answer
362 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
0
votes
2answers
54 views

Subset of A Regular Language

I need to show that a subset of a regular language is regular or not. I think it may not be regular but I could not find a counter example. Do you have any simple example to prove that? Thanks in ...
0
votes
2answers
35 views

Regular Language Operation

I need to show that the given regular language is closed under the following operation. For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* } I do not ...
0
votes
1answer
35 views

Give an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct.

Given an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct. We define the matrix as follows. Let $L \subset \Gamma^*$ where $\Gamma$ is alphabet. Then the ...
0
votes
1answer
42 views

Construc a DFA for given language

The given language is this. $$L = \{a^nb : n \geq 0\}$$ Let $M = \left<\{q_0,q_1,q_2\},q_0,\Gamma=\{a,b\},\delta,\{q_2\}\right>$ be a DFA, where $q_0$ is the initial state, $q_2$ is the accept ...
0
votes
2answers
87 views

Can someone explain this automaton?

I have a question about constructing an automaton for given language: $$L = \{000, 010, 100, 110\}$$ Solution for this was given below. Can anyone explain why this automaton accepts the language? This ...
1
vote
2answers
55 views

If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$?

Given the words $v,w \in \sum^*$, is this correct? If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$ If $vw^2 = wv^2$ then $v=w$ For one, I tried $v=\epsilon, w=\epsilon$ and it worked, and ...
0
votes
1answer
99 views

Construct an automaton by using sliding window method

Given alphabet $\Gamma = \{0,1\}$, let $L = \{\omega : All\ words\ ending\ 010\}$ be a language. Find an automaton. I have to find an automaton using sliding window method.. First I need some ...
3
votes
3answers
321 views

Matrix representation of Automata

Is anyone know if there is any tutorial for the matrix representation of automata?? I am taking a theoritical computer science in this semester and the professor uses the matrix in his lecture. I ...
1
vote
3answers
76 views

Why is this the $L(M)$ of this DFA?

Why is this the $L(M)$ of this DFA? Can someone please explain it? I am new to this course. When I tried alone answering the question of "What is special about the words that get accepted by this ...
4
votes
1answer
1k views

Give a push down Automata for this language: the length of is odd and it's middle symbol is 0

Give a push down automaton for this language: {w| the length of w is odd and it's middle symbol is 0} Here is the CFG I wrote for this language: ...
0
votes
1answer
68 views

Automata and power series

I am taking a class on Automata and Formal Languages and I need to solve an exercise, but I have no idea where to start from. It sounds like this: Decide the coefficients of the words in ...
0
votes
1answer
422 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
0
votes
1answer
41 views

Is this language regular ? [automata]

Is this a regular language : $$L = \{w : w \in \{a,b\}^*\text{ and }abw = wba\}$$ Does my automata only need to start with $a$ and $b$, then loop on $a,b$ and finish with $b\to a$, or do I don't ...
0
votes
2answers
356 views

Is it true that any infinite subset of a non-regular unary language is non-regular?

My question is very similar to this: Is there a subset of a non regular language that is regular My claim is that because the subset is infinite, Myhill Nerode says that the language is not regular. ...
0
votes
2answers
131 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
2answers
127 views

Finite state automata for two regular languages

I have to draw FSAs that accept the following languages over {0,1} and {a, b} (0 | 1)* a* | b* Now for 1, the language is just any word that consists of 1s and 0s but it also contains the empty ...
2
votes
0answers
31 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
2
votes
1answer
436 views

Verification: DFA/NFA that accepts all strings over $\{0,1\}$ with exactly one block of $00$

I am trying to design a DFA or NFA that accepts all strings over $\Sigma = \{0,1\}$ in which the block $00$ appears only once. Here is what I've tried. Can you verify that this accepts all string ...
1
vote
1answer
45 views

Post-concatenation of the languages represented by the null set

I have a small question regarding concatenation of regular languages: Is it true that the concatenation $L\varnothing$, where $L$ is any regular language, result in $\varnothing$? Namely, does ...
2
votes
1answer
73 views

NFA from grammar productions

Based on this grammar: \begin{align} G = (\{S,A,B\}, \{a,b, c\}, S, P) \end{align} \begin{matrix} \\P: \\S → abaS | cA \\A → bA | cB | aa \\B → bB | cA | bb \end{matrix} I created this NFA: ...
1
vote
0answers
118 views

Constructing an NFA accepted by a grammar

Contruct an NFA of the language accepted by the grammar below. $$G=(\{S,A,B\}, \{a,b,c\},S,P)$$ $P: S\rightarrow abaS\ \ | \ cA\\ \ \ \ \ \ \ A\rightarrow bA\ \ | \ cB \ \ | \ aa\\ \ \ \ \ \ ...
0
votes
1answer
221 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this 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 ...
1
vote
1answer
53 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
31 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...
1
vote
1answer
28 views

Regular expression for a language

I made a regular expression to match this language but I'm not sure it's right. Perhaps someone can show me where it deviates. The language: $L = {a^{n} c b^{m} (cc)^{p} : n \geq 1, m \leq 1, p\geq ...
0
votes
2answers
78 views

Constructing regular grammar

I'm trying to make a regular grammar for this language: $$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$ Where the alphabet is $ \Sigma = \{a,b,c\}$ It seemed like right-linear. This may be ...
4
votes
2answers
187 views

context free grammar problem

$L$ is the context free grammar over $\{a, b\}$ $S \rightarrow aSb \; | \;bR \; |\;Ra$ $R \rightarrow bR \;|\;aR\;|\;\epsilon$ Briefly describe this CFG with English sentences and prove your ...
0
votes
2answers
63 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
1
vote
2answers
164 views

interpreting language for finite state machine

Can someone explain to me what this means in clear english and maybe give me a hint for how to make a NDFSM (non-deterministic finite state machine) that accepts this language? I understand that the 3 ...
0
votes
2answers
61 views

$2^E$ where $E$ is a set

I'm studing the definition of automaton $G=(X, E, f, \Gamma, x_o, X_m)$ where $X$ is the set of states and $E$ is the set of events. My sources report that $\Gamma:X \rightarrow 2^E$ is the indicator ...
1
vote
1answer
137 views

Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
0
votes
2answers
516 views

Finite automata for any even number of a's followed by any even number of b's

I'm new to formal languages. I'm stuck with the following question. Any help is appreciated. Find finite automata for $$L = \{a^i b^j \mid i, j\text{ are even, }j\ge0\}$$ Thank you
4
votes
2answers
122 views

Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and $s$ has length $i$}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
2
votes
1answer
561 views

Does closure under the union and concatenation operations imply closure under the star operation?

Given any two languages $A$ and $B$, recall the following regular operations: Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Concatenation: $A \circ B = \{xy \mid x \in A \text{ ...
1
vote
2answers
403 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
2answers
99 views

The Relation of Cellular Automata to Languages

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language? In probabilistic cellular automata, are ...
0
votes
1answer
68 views

Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

In the Book Infinite Words (homepage) it is proofed that: If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1) $X$ is closed (2) $X$ is recognized by a ...
0
votes
1answer
211 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
1
vote
2answers
320 views

Converting from NFA to a regular expression.

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows $$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) ...
2
votes
1answer
72 views

Is there an (explicit?) bijection from the set of all automatons to the set of all regular expressions that conserves the recongnised language

Let $\Sigma$ be an alphabet, $R$ be the set of regular expressions on $\Sigma$ (that is, trees with leave's values in $\left\{\varepsilon\right\}\cup \Sigma$ and three types of interior nodes, one ...
0
votes
2answers
847 views

To design a Finite State machine

Design a FSM for a binary number in which the input is valid if no. of 0's divisible by 5 and no. of 1's divisible by 3
1
vote
2answers
103 views

Finite automata and languages question

I have attempted these few simple questions, can someone let me know if this is correct please? If not please provide the answer as I learn better that way and if possible explain. i) FA1 Start = ...
2
votes
0answers
60 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
53 views

Quality of Reduction of finite automata

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a ...